Pair with difference K

Count unordered index pairs with absolute difference exactly K using frequency maps.

dictionary set counting hashmap pair

Write a function `count_pairs_with_diff(nums, k)` that takes a list of integers `nums` and a non-negative integer `k`, and returns the number of unordered index pairs `(i, j)` such that `i != j` and `abs(nums[i] - nums[j]) == k`. Each pair should be counted only once regardless of index order. Duplicate values count as distinct positions, so every valid pair of indices is counted. The solution must run in O(n) time and O(n) space.

**Input:**
- `nums`: list of integers, length between 0 and 100,000.
- `k`: integer, `0 <= k <= 10^9`.

**Output:**
- Integer: number of valid unordered index pairs.

**Examples:**
```python
count_pairs_with_diff([1, 5, 3, 4, 2], 2) == 3
count_pairs_with_diff([1, 1, 1], 0) == 3
count_pairs_with_diff([1, 1, 2, 2, 3, 3], 1) == 8
```

**Complexity:** O(n) time, O(n) space.

Constraints

0 <= len(nums) <= 100,000
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^9

Example

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

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Count frequencies of each number using a dictionary.

For k == 0, each frequency f contributes f*(f-1)//2 pairs.

For k > 0, for each unique value x, add freq[x] * freq[x+k], but avoid double counting by only iterating over keys where x < x+k.

Test Results

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