Count Number of Pairs With Absolute Difference K

easy array hash table counting

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 |x| is x when x ≥ 0 and −x when x < 0.

Inputnums = [1,2,2,1], k = 1

Output4

Pairs of indices with an absolute difference of 1: (0,1), (0,2), (1,3), (2,3) — four in total.

nums (comma-separated)

def countKDifference(nums, k):
    count = {}          # value -> how many times seen so far
    pairs = 0
    for x in nums:
        # x can pair with an earlier value of x-k or x+k
        pairs += count.get(x - k, 0)
        pairs += count.get(x + k, 0)
        count[x] = count.get(x, 0) + 1
    return pairs

function countKDifference(nums, k) {
  const count = new Map();   // value -> how many times seen so far
  let pairs = 0;
  for (const x of nums) {
    // x can pair with an earlier value of x-k or x+k
    pairs += count.get(x - k) || 0;
    pairs += count.get(x + k) || 0;
    count.set(x, (count.get(x) || 0) + 1);
  }
  return pairs;
}

int countKDifference(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    int pairs = 0;
    for (int x : nums) {
        // x can pair with an earlier value of x-k or x+k
        pairs += count.getOrDefault(x - k, 0);
        pairs += count.getOrDefault(x + k, 0);
        count.merge(x, 1, Integer::sum);
    }
    return pairs;
}

int countKDifference(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    int pairs = 0;
    for (int x : nums) {
        // x can pair with an earlier value of x-k or x+k
        pairs += count.count(x - k) ? count[x - k] : 0;
        pairs += count.count(x + k) ? count[x + k] : 0;
        count[x]++;
    }
    return pairs;
}

Explanation

The brute-force idea is to test every pair of indices, which costs O(n²). We can do better with a single pass and a hash map of counts.

Scan the array left to right. Keep a map count that records, for every value seen so far, how many times it appeared. When we arrive at a new element x, any earlier index i forms a valid pair with the current index j exactly when |nums[i] − x| == k. That means the earlier value was either x − k or x + k.

So we add count[x − k] and count[x + k] to our running pairs total — these are precisely the earlier elements that pair with x. Because we only look at elements already in the map, every counted pair has i < j, so nothing is double-counted.

After tallying, we record the current value by doing count[x] += 1, making it available for future elements.

Example: nums = [1,2,2,1], k = 1. The first 1 finds nothing. The first 2 sees one earlier 1 (1 pair). The second 2 sees one earlier 1 (1 more). The last 1 sees two earlier 2s (2 more). Total = 4.

Time: O(n) Space: O(n)