LeetCode 532 - K-diff Pairs in an Array

LeetCode Problem 532

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

The problem asks us to count how many unique pairs of integers in the array have an absolute difference equal to k.

A pair is considered valid if:

• The two elements come from different indices.
• The absolute difference between the two values is exactly k.

The important detail is that we only count unique pairs. This means that duplicate values in the array should not cause the same pair to be counted multiple times.

For example, in:

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

The pair (1,3) appears more than once because there are two occurrences of 1, but it should still only be counted once.

The input consists of:

• An integer array nums
• An integer k

The output is a single integer representing the number of distinct k-diff pairs.

The constraints are relatively moderate:

• nums.length <= 10^4
• Values can be negative
• k can be zero

These constraints tell us that an O(n^2) brute-force solution might pass in some languages for smaller inputs, but it is not ideal. The problem clearly expects a more efficient approach using hashing, sorting, or two pointers.

Several edge cases are important:

• k = 0, where we are looking for duplicate numbers
• Arrays with many duplicates
• Negative numbers
• Empty or single-element effective scenarios
• Large values that still fit safely within integer ranges

One especially important observation is that k is guaranteed to be non-negative. Since the problem uses absolute difference, negative k would never make sense anyway.

Approaches

Brute Force Approach

The most direct solution is to examine every possible pair of indices (i, j) where i != j.

For each pair:

1. Compute abs(nums[i] - nums[j])
2. If the difference equals k, store the pair in a set to avoid duplicates

Because (1,3) and (3,1) represent the same logical pair, we would normalize the pair before storing it, typically by storing (min(a,b), max(a,b)).

This approach is correct because it explicitly checks all valid combinations. However, it is inefficient because there are O(n^2) possible pairs.

With n = 10^4, this can lead to about 100 million comparisons, which is unnecessarily expensive.

Optimal Approach, Hash Set / Frequency Map

The key insight is that for a number x, we only need to know whether x + k exists.

Instead of comparing every pair, we can use hashing for constant-time lookups.

There are two separate cases:

• When k > 0, we count distinct values x where x + k exists.
• When k == 0, we count numbers that appear more than once.

A frequency map is ideal because:

• It gives constant-time existence checks
• It tracks duplicate counts naturally
• It avoids repeated pair counting

This reduces the time complexity to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Checks every pair and uses a set for uniqueness
Optimal	O(n)	O(n)	Uses a hash map for frequency counting and fast lookups

Algorithm Walkthrough

Optimal Hash Map Algorithm

1. First, create a frequency map of all numbers in the array.

The frequency map allows us to:

• Quickly determine whether a value exists
• Know how many times a value appears

For example:

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

produces:

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

2. Initialize a counter variable called pairs.

This variable will store the number of unique k-diff pairs. 3. Handle the case where k == 0.

When k is zero, we are looking for pairs like (x, x).

Since indices must be different, the number must appear at least twice.

For every number in the frequency map:

• If its frequency is greater than 1, increment the answer.

4. Handle the case where k > 0.

For every unique number x in the frequency map:

• Check whether x + k exists in the map.
• If it does, increment the answer.

This works because each unique starting value contributes exactly one unique pair. 5. Return the final count.

Why it works

The algorithm works because every unique k-diff pair can be represented as (x, x + k).

For k > 0, iterating through unique numbers ensures that every pair is counted exactly once.

For k == 0, a valid pair exists only when a number appears multiple times.

The hash map guarantees efficient existence checks while naturally eliminating duplicate counting.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        frequency = Counter(nums)
        pairs = 0

        if k == 0:
            for count in frequency.values():
                if count > 1:
                    pairs += 1
        else:
            for number in frequency:
                if number + k in frequency:
                    pairs += 1

        return pairs

The implementation begins by constructing a Counter, which is a specialized hash map that stores frequencies of elements.

The variable pairs tracks the total number of valid unique pairs.

The logic then splits into two branches.

When k == 0, we search for duplicate numbers. Every number with frequency greater than one contributes exactly one valid pair.

When k > 0, we iterate through each unique number and check whether number + k exists in the frequency map. If it does, we have found a valid unique pair.

Because the iteration occurs only over unique keys, duplicate pairs are never counted multiple times.

Go Solution

func findPairs(nums []int, k int) int {
	frequency := make(map[int]int)

	for _, num := range nums {
		frequency[num]++
	}

	pairs := 0

	if k == 0 {
		for _, count := range frequency {
			if count > 1 {
				pairs++
			}
		}
	} else {
		for number := range frequency {
			if _, exists := frequency[number+k]; exists {
				pairs++
			}
		}
	}

	return pairs
}

The Go implementation follows the same logic as the Python solution.

A map[int]int is used instead of Python's Counter.

Go maps return two values during lookup:

value, exists := map[key]

We only care about whether the key exists, so the value is ignored using _.

Since the constraints are well within Go's integer range, integer overflow is not a concern here.

Worked Examples

Example 1

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

Step 1: Build frequency map

Number	Frequency
1	2
3	1
4	1
5	1

Step 2: Check pairs

Current Number	Check For	Exists?	Pair Count
1	3	Yes	1
3	5	Yes	2
4	6	No	2
5	7	No	2

Final answer:

2

Valid pairs are:

(1,3), (3,5)

Example 2

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

Frequency map

Number	Frequency
1	1
2	1
3	1
4	1
5	1

Pair checking

Current Number	Check For	Exists?	Pair Count
1	2	Yes	1
2	3	Yes	2
3	4	Yes	3
4	5	Yes	4
5	6	No	4

Final answer:

4

Example 3

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

Frequency map

Number	Frequency
1	2
3	1
5	1
4	1

Duplicate checking

Number	Frequency	Valid Pair?	Pair Count
1	2	Yes	1
3	1	No	1
5	1	No	1
4	1	No	1

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Building the frequency map and iterating through keys are both linear
Space	O(n)	The hash map may store all unique numbers

The algorithm performs a single pass to build the frequency map and another pass through unique keys. Hash map operations are average-case constant time, so the overall runtime is linear.

The space complexity is linear because the frequency map may contain every element if all numbers are unique.

Test Cases

from typing import List

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        from collections import Counter

        frequency = Counter(nums)
        pairs = 0

        if k == 0:
            for count in frequency.values():
                if count > 1:
                    pairs += 1
        else:
            for number in frequency:
                if number + k in frequency:
                    pairs += 1

        return pairs

solution = Solution()

assert solution.findPairs([3,1,4,1,5], 2) == 2  # Example 1
assert solution.findPairs([1,2,3,4,5], 1) == 4  # Example 2
assert solution.findPairs([1,3,1,5,4], 0) == 1  # Example 3

assert solution.findPairs([1,1,1,1], 0) == 1  # Multiple duplicates, one unique pair
assert solution.findPairs([1,2,3,4], 5) == 0  # No valid pairs
assert solution.findPairs([], 1) == 0  # Empty array
assert solution.findPairs([1], 0) == 0  # Single element
assert solution.findPairs([-1,-2,-3], 1) == 2  # Negative numbers
assert solution.findPairs([1,1,1,2,2], 1) == 1  # Duplicate values with k > 0
assert solution.findPairs([6,3,5,7,2,3,3,8,2,4], 2) == 5  # Mixed duplicates

Test	Why
[3,1,4,1,5], k=2	Validates standard duplicate handling
[1,2,3,4,5], k=1	Validates consecutive pairs
[1,3,1,5,4], k=0	Validates duplicate counting logic
[1,1,1,1], k=0	Ensures duplicates count once
[1,2,3,4], k=5	Validates no-match scenario
[], k=1	Validates empty input handling
[1], k=0	Validates minimum-size input
[-1,-2,-3], k=1	Confirms negative numbers work correctly
[1,1,1,2,2], k=1	Ensures uniqueness despite duplicates
[6,3,5,7,2,3,3,8,2,4], k=2	Stress-style mixed duplicate case

Edge Cases

Case 1, k == 0

This is the most important special case in the problem.

Normally, we search for numbers separated by exactly k. However, when k is zero, valid pairs consist of identical values.

A naive implementation might incorrectly count every duplicate occurrence separately. For example:

[1,1,1,1]

should produce only one unique pair (1,1).

The implementation handles this correctly by counting how many numbers appear more than once, rather than counting combinations of indices.

Case 2, Duplicate Values with k > 0

Consider:

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

The pair (1,3) exists many times if we consider indices, but the problem only wants unique value pairs.

A brute-force implementation can easily overcount.

The hash-map approach avoids this issue because it iterates only through unique keys in the frequency map.

Case 3, Negative Numbers

The array may contain negative integers:

nums = [-3,-2,-1]
k = 1

Valid pairs are:

(-3,-2), (-2,-1)

The algorithm works naturally with negative values because hash maps support negative keys without any special handling.

Case 4, No Valid Pairs

Some arrays contain no valid differences:

nums = [1,5,9]
k = 2

The implementation correctly returns 0 because no number + k values exist in the frequency map.

Case 5, Single Element Arrays

A single element can never form a valid pair because the indices must be different.

For example:

nums = [10]
k = 0

returns 0.

The implementation handles this naturally because no frequency exceeds one and no complementary value exists.