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:

1
2
3
4
5
6
7

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:

1
2
3
4
5

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

Example 3:

1
2
3
4
5
6

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 - Naive

A simple but inefficient solution involves performing a linear search for each element e1 to find e2 = e1 + k in the rest of the array, resulting in an O(n^2) time complexity. However, we can improve upon this.

Method 2 - 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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.

Method 3 - Using Hashset

Here are the steps:

  1. Use a HashSet to store the elements seen during a single pass through the array.
  2. For each element e, check if (e-K) or (e+K) is already in the HashSet. If so, increment a count.
  3. Add the current element e to the HashSet.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public class Solution {
    public int countKDifference(final int[] A, final int K) {
        final HashSet<Integer> hs = new HashSet<>();
        int count = 0;

        for (int i = 0; i < A.length; i++) {
            if (hs.contains(A[i] - K)) {
                count++;
            }
            if (hs.contains(A[i] + K)) {
                count++;
            }

            hs.add(A[i]);
        }
        return count;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def countKDifference(nums, k):
    seen = set()
    count = 0

    for num in nums:
        if (num - k) in seen:
            count += 1
        if (num + k) in seen:
            count += 1
        seen.add(num)

    return count

Method 4 - Using Sorting

If space is limited, an alternative solution uses O(1) space and O(n log k) time. Instead of a linear search for e2 = e1 + k, we employ an optimal binary search.

  1. Sort the array, which takes O(n log n) time.
  2. For each element e1 in the sorted array, search for an element e2 > e1 such that A[e2] - A[e1] = k.

By performing a binary search for e2 from e1 + 1 to e1 + diff in the sorted array, we limit our search to O(log k) time for each element. The overall time complexity becomes O(n log n) + O(n log k). If k > n, the time complexity of this algorithm is O(n log k) with O(1) space.

For finding pairs with the minimum difference, you can refer to the solution in Min difference pairs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Solution {
    public int countKDifference(final int[] A, final int diff) {
        Arrays.sort(A);
        int count = 0;

        for (int i = 0; i < A.length; i++) {
            int matchKey = A[i] + diff;
            int matchIndex = binarySearch(A, Math.min(i + 1, A.length - 1),
                Math.min(i + diff, A.length - 1), matchKey);
            count += (matchIndex != -1) ? 1 : 0;
        }

        return count;
    }
    private int binarySearch(final int[] A, int l, int r, final int key) {
        while (l <= r) {
            int m = (l + r) / 2;
            if (A[m] == key) {
                return m;
            } else if (key < A[m]) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def countKDifference(arr, diff):
    arr.sort()
    count = 0

    for i in range(len(arr)):
        match_key = arr[i] + diff
        left = min(i + 1, len(arr) - 1)
        right = min(i + diff, len(arr) - 1)
        if binary_search(arr, left, right, match_key) != -1:
            count += 1

    return count


def binary_search(arr, left, right, key):
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == key:
            return mid
        elif arr[mid] < key:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Complexity

  • ⏰ Time complexity: O(n log k)
  • 🧺 Space complexity: O(1)