Problem

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.

The value of |x| is defined as:

  • x if x >= 0.
  • -x if x < 0.

Examples

Example 1:

Input: nums = [1,2,2,1], k = 1
Output: 4
Explanation: The pairs with an absolute difference of 1 are:
- [1̲,2̲,2,1]
- [1̲,2,2̲,1]
- [1,2̲,2,1̲]
- [1,2,2̲,1̲]

Example 2:

Input:
nums = [1,3], k = 3
Output:
 0
Explanation: There are no pairs with an absolute difference of 3.

Example 3:

Input: nums = [3,2,1,5,4], k = 2
Output: 3
Explanation: The pairs with an absolute difference of 2 are:
- [3̲,2,1̲,5,4]
- [3̲,2,1,5̲,4]
- [3,2̲,1,5,4̲]

Solution

Method 1 - Using HashMap

Here is the approach:

  1. Use a HashMap:
    • We can use a HashMap to keep track of the frequency of each element in nums as we iterate through the array.
    • For each element num in nums, check if (num + k) or (num - k) exists in the HashMap.
    • If it does, increment the result by the frequency of those elements.
    • Add the current element to the HashMap.
  2. Count Pairs:
    • As we iterate, for each element num, if num + k or num - k exists, it means there are pairs that satisfy the condition.

Code

Java
public class Solution {
    public int countKDifference(int[] nums, int k) {
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        int count = 0;

        for (int num : nums) {
            if (freqMap.containsKey(num + k)) {
                count += freqMap.get(num + k);
            }
            if (freqMap.containsKey(num - k)) {
                count += freqMap.get(num - k);
            }

            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        return count;
    }
}
Python
def countKDifference(nums, k):
    freq_map = {}
    count = 0

    for num in nums:
        if num + k in freq_map:
            count += freq_map[num + k]
        if num - k in freq_map:
            count += freq_map[num - k]

        if num in freq_map:
            freq_map[num] += 1
        else:
            freq_map[num] = 1

    return count

Complexity

  • Time: O(n), where (n) is the number of elements in the array nums, since we are iterating through the array and using a HashMap for constant time get and put operations.
  • Space: O(n) as we are storing elements in a HashMap.