# LeetCode 532: K-diff Pairs in an Array

## Problem Restatement

We are given an integer array `nums` and an integer `k`.

We need to count the number of unique pairs `(a, b)` such that:

```python
abs(a - b) == k
```

The pair must use two different indices in the array.

The word unique is important. If the same value pair appears many times because of duplicates, we count it only once.

The problem guarantees:

```python
0 <= k
```

So we do not need to handle negative `k`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` and an integer `k` |
| Output | The number of unique k-diff pairs |
| Pair rule | `abs(nums[i] - nums[j]) == k` |
| Index rule | `i != j` |
| Uniqueness | Same value pair is counted once |

Function shape:

```python
def findPairs(nums: list[int], k: int) -> int:
    ...
```

## Examples

Consider:

```python
nums = [3, 1, 4, 1, 5]
k = 2
```

The valid unique pairs are:

```python
(1, 3)
(3, 5)
```

Although `1` appears twice, the pair `(1, 3)` is still counted only once.

So the answer is:

```python
2
```

Now consider:

```python
nums = [1, 2, 3, 4, 5]
k = 1
```

The valid pairs are:

```python
(1, 2)
(2, 3)
(3, 4)
(4, 5)
```

So the answer is:

```python
4
```

For `k = 0`:

```python
nums = [1, 3, 1, 5, 4]
k = 0
```

We need pairs with equal values.

The only value that appears at least twice is `1`.

So the only unique pair is:

```python
(1, 1)
```

The answer is:

```python
1
```

## First Thought: Compare Every Pair

The most direct approach is to compare every pair of indices.

For each `i`, compare it with every `j > i`.

If:

```python
abs(nums[i] - nums[j]) == k
```

then add the value pair to a set.

For example, store pairs in sorted order:

```python
(min(nums[i], nums[j]), max(nums[i], nums[j]))
```

Then the size of the set is the answer.

This is correct, but it takes `O(n^2)` time.

Since `nums.length` can be up to `10^4`, quadratic time is too slow.

## Key Insight

For `k > 0`, each unique pair can be represented by its smaller value.

If the smaller value is `x`, then the larger value must be:

```python
x + k
```

So we only need to know whether both values exist in the array.

For example, if `k = 2` and `x = 3`, then the pair is:

```python
(3, 5)
```

So the question becomes:

“Does `x + k` also exist?”

For `k = 0`, the logic is different.

A pair `(x, x)` is valid only if `x` appears at least twice.

So frequency counting handles both cases cleanly.

## Algorithm

Build a frequency map:

```python
value -> count
```

Then handle two cases.

If `k == 0`:

1. Count how many values appear at least twice.
2. Each such value forms one unique pair `(value, value)`.

If `k > 0`:

1. For each unique value `x` in the frequency map.
2. Check whether `x + k` exists in the frequency map.
3. If it exists, count one pair.

Return the count.

## Correctness

The frequency map records exactly which values appear in the array and how many times each value appears.

When `k = 0`, a valid pair must have equal values because the absolute difference is zero. Such a pair needs two different indices, so the value must appear at least twice. The algorithm counts exactly the values whose frequency is at least two, so it counts exactly all unique `0`-diff pairs.

When `k > 0`, every valid pair has two distinct values. Let the smaller value be `x`. Then the larger value must be `x + k`. Therefore, the pair exists exactly when both `x` and `x + k` appear in the array. The algorithm checks this condition for every unique `x`.

Each pair is counted once because it is counted only from its smaller value. The larger value does not count the same pair again, because it would look for `larger + k`, not `larger - k`.

Therefore, the algorithm returns the number of unique k-diff pairs.

## Complexity

Let `n = len(nums)` and `u` be the number of unique values.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Build the frequency map, then scan unique values |
| Space | `O(u)` | Store one count per unique value |

Since `u <= n`, the space complexity is also `O(n)` in the worst case.

## Implementation

```python
from collections import Counter

class Solution:
    def findPairs(self, nums: list[int], k: int) -> int:
        freq = Counter(nums)

        if k == 0:
            return sum(1 for count in freq.values() if count >= 2)

        answer = 0

        for x in freq:
            if x + k in freq:
                answer += 1

        return answer
```

## Code Explanation

We first count the values:

```python
freq = Counter(nums)
```

For example:

```python
nums = [3, 1, 4, 1, 5]
```

gives:

```python
{
    3: 1,
    1: 2,
    4: 1,
    5: 1,
}
```

If `k == 0`, we need duplicate values:

```python
return sum(1 for count in freq.values() if count >= 2)
```

Each value with count at least `2` forms one pair `(x, x)`.

If `k > 0`, we scan each unique value:

```python
for x in freq:
```

Then we check whether the matching larger value exists:

```python
if x + k in freq:
```

If it exists, `(x, x + k)` is a valid unique pair.

## Sorting Version

We can also solve the problem by sorting and using two pointers.

```python
class Solution:
    def findPairs(self, nums: list[int], k: int) -> int:
        nums.sort()

        left = 0
        right = 1
        answer = 0

        while right < len(nums):
            if left == right or nums[right] - nums[left] < k:
                right += 1
            elif nums[right] - nums[left] > k:
                left += 1
            else:
                answer += 1
                left_value = nums[left]
                right_value = nums[right]

                while left < len(nums) and nums[left] == left_value:
                    left += 1

                while right < len(nums) and nums[right] == right_value:
                    right += 1

        return answer
```

This version also counts unique pairs, but the hash table solution is simpler.

Its complexity is:

| Metric | Value |
|---|---:|
| Time | `O(n log n)` |
| Space | `O(1)` or `O(n)`, depending on sorting implementation |

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findPairs([3, 1, 4, 1, 5], 2) == 2
    assert s.findPairs([1, 2, 3, 4, 5], 1) == 4
    assert s.findPairs([1, 3, 1, 5, 4], 0) == 1
    assert s.findPairs([1, 1, 1, 1], 0) == 1
    assert s.findPairs([1, 2, 4, 4, 3, 3, 0, 9, 2, 3], 3) == 2
    assert s.findPairs([-1, -2, -3], 1) == 2

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[3,1,4,1,5]`, `k = 2` | Standard duplicate case |
| `[1,2,3,4,5]`, `k = 1` | Consecutive increasing values |
| `[1,3,1,5,4]`, `k = 0` | Equal-value pair case |
| `[1,1,1,1]`, `k = 0` | Many duplicates but one unique pair |
| Mixed duplicates | Checks uniqueness with repeated values |
| Negative numbers | Confirms absolute difference logic still works |