algoadvance

Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.

Clarifying Questions

  1. What is the range of the input array length and values?
    • Constraints:
      • 1 <= nums.length <= 200
      • 1 <= nums[i] <= 100
      • 0 <= k <= 100
  2. Can the array contain duplicate elements?
    • Yes, the array can contain duplicate elements.
  3. Would there ever be negative values for k?
    • No, k is guaranteed to be non-negative.
  4. What should the function return if no such pairs are found?
    • The function should return 0 if no such pairs are found.

Strategy

  1. Brute Force Approach:
    • Iterate through every possible pair (i, j) with i < j.
    • Check if the absolute difference |nums[i] - nums[j]| is equal to k.
    • If it is, count this pair.
  2. Optimized Approach using a Frequency Map:
    • Use a hashmap to store the frequency of each number in the array.
    • Iterate through the array and for each element num, check if (num + k) or (num - k) exists in the hashmap.
    • The count of both these numbers, if they exist, gives the number of pairs with absolute difference k.

Code

Here’s the implementation using the optimized approach:

def countKDifference(nums, k):
    from collections import defaultdict
    
    freq_map = defaultdict(int)
    count = 0
    
    for num in nums:
        # Check for pairs with (num + k)
        count += freq_map[num + k]
        # Check for pairs with (num - k)
        count += freq_map[num - k]
        
        # Update the frequency map
        freq_map[num] += 1
    
    return count

# Example usage
nums = [1, 2, 2, 1]
k = 1
print(countKDifference(nums, k))  # Output: 4

Time Complexity

This efficient approach ensures that we only pass through the list a constant number of times and check for conditions in constant time, making it very suitable given the problem constraints.

Try our interview co-pilot at AlgoAdvance.com