Count pairs with given difference

Efficiently count unordered pairs whose absolute difference equals a target k.

hash map counting arrays

Write a function `count_pairs_with_difference(nums, k)` that takes a list of integers `nums` (each between -10^6 and 10^6) and an integer `k` (0 <= k <= 10^6). The function must return the number of **unordered pairs** `(i, j)` with `i < j` such that the absolute difference `|nums[i] - nums[j]| == k`.

Unordered means that the pair `(i, j)` is considered the same as `(j, i)` and should be counted only once. Duplicate values in the list count as distinct elements; if the same value appears multiple times, each distinct index pair that satisfies the condition counts separately.

**Efficiency requirement:** Implement the function so that it runs in O(n) average time (using a dictionary), not O(n^2).

**Assumptions:** The input list will contain at least 1 element. The target difference `k` is non-negative.

Constraints

1 <= len(nums) <= 10^5
-10^6 <= nums[i] <= 10^6
0 <= k <= 10^6
The expected time complexity is O(n) average, with O(n) space.

Example

```python
>>> count_pairs_with_difference([1, 5, 3, 4, 2], 2)
3
>>> count_pairs_with_difference([1, 1, 1], 0)
3
>>> count_pairs_with_difference([], 5)
0
```

12 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

If you use a dictionary to memorize the frequency of each number, you can check for both `num + k` and `num - k`.

When k=0, be careful not to count a pair twice. Use combinations of counts: for a value with frequency f, the number of pairs is f*(f-1)//2.

Iterate once, adding each new number to the frequency map after checking against existing frequencies to avoid double counting.

You can also use `collections.Counter` and sum over values, but the one-pass method is direct.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.