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:

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:

0 <= k

So we do not need to handle negative k.

Input and Output

Function shape:

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

Examples

Consider:

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

The valid unique pairs are:

(1, 3)
(3, 5)

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

So the answer is:

2

Now consider:

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

The valid pairs are:

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

So the answer is:

4

For k = 0:

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:

(1, 1)

The answer is:

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:

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

then add the value pair to a set.

For example, store pairs in sorted order:

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

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:

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

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.

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

Implementation

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:

freq = Counter(nums)

For example:

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

gives:

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

If k == 0, we need duplicate values:

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:

for x in freq:

Then we check whether the matching larger value exists:

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.

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:

Testing

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