Count Number of Pairs With Absolute Difference K

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

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.

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

Java

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;
    }
}

Python

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](minimum-absolute-difference).

Code

Java

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;
    }
}

Python

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)