K-diff Pairs in an Array: Hash Map for Target Differences

Given an array of integers nums and an integer k, you need to find the number of unique k-diff pairs in the array. A k-diff pair is a pair of integers (nums[i], nums[j]) where |nums[i] - nums[j]| = k and i != j. The pair (a, b) is considered the same as (b, a), and you only count unique value pairs.

This is LeetCode 532: K-diff Pairs in an Array, a medium-difficulty problem that tests your ability to efficiently count pairs with a specific difference. It is a natural extension of Two Sum, but instead of a target sum you are looking for a target difference.

The problem

You are given nums = [3, 1, 4, 1, 5] and k = 2. You need to count how many unique pairs of numbers have an absolute difference of exactly 2. The valid pairs are (1, 3) and (3, 5), so the answer is 2. Notice that even though 1 appears twice, the pair (1, 3) is only counted once.

The key insight

The brute force approach checks every pair in O(n^2). But we can do much better by reframing the problem. Instead of checking all pairs, build a frequency counter (hash map) of all values. Then for each unique key num in the counter, check whether num + k also exists. If it does, that is one valid pair. This avoids double-counting because we always look in one direction (upward by k).

There is one special case: when k = 0, you are looking for duplicate values. A pair (a, a) is only valid if a appears at least twice, so you check whether the count of a is 2 or more.

The solution

from collections import Counter

def find_pairs(nums, k):
    counter = Counter(nums)
    result = 0
    for num in counter:
        if k > 0 and num + k in counter:
            result += 1
        elif k == 0 and counter[num] >= 2:
            result += 1
    return result

Step-by-step walkthrough

Let's trace through nums = [3, 1, 4, 1, 5] with k = 2. First we build the counter, then we iterate over each unique key and check if num + k exists.

We checked each unique key exactly once and found 2 valid pairs. The duplicate value 1 did not cause any double-counting because the counter stores unique keys.

Complexity analysis

Time: O(n). Building the counter takes one pass through the array. Iterating over unique keys is at most O(n). Each hash map lookup is O(1) on average, so the total is O(n).

Space: O(n). The counter stores up to n entries in the worst case (all unique values).

The building blocks

1. Frequency counter

Building a Counter (or dictionary of counts) from an array is a fundamental pattern. You see it in anagram detection, top-k-frequent elements, and any problem that asks about duplicates or frequencies. The key operation is: iterate once, count everything, then query the counts in O(1).

counter = Counter(nums)

2. Complement lookup in a counter

Instead of checking every pair, you compute the value you need (num + k) and look it up directly. This is the same idea behind Two Sum's target - num lookup, adapted for differences instead of sums. The counter doubles as both the set of seen values and the frequency tracker.

if num + k in counter:
    result += 1

Edge cases

• k = 0: You need pairs where both values are the same, so you count keys with frequency 2 or more. Without this special case, every key would match itself.
• Negative k: The problem guarantees k is non-negative, but if it could be negative, you would take abs(k) first since |a - b| = |b - a|.
• All duplicates: An array like [1, 1, 1, 1] with k = 0 returns 1, not 6. You are counting unique value pairs, not index pairs.
• Single element: An array with one element always returns 0 since you need at least two elements to form a pair.
• Large k with small range: If k is larger than the difference between max and min values, no pairs exist.

From understanding to recall

K-diff Pairs feels easy once you see the counter approach. "Just count frequencies and check complements." But when a harder problem uses the same complement-in-a-counter trick, like subarray sum equals K with prefix sums, you want this pattern to fire automatically. That is what spaced repetition is for. You practice building the counter and checking num + k from memory at increasing intervals. After a few cycles, the pattern is locked in, and you reach for it instinctively whenever a problem asks about pairs with a target relationship.

Related posts

• Two Sum - The classic complement lookup problem, using a hash map to find pairs with a target sum
• Contains Duplicate II - Another hash map problem that tracks indices within a sliding window to detect nearby duplicates
• Find All Anagrams in a String - Uses a frequency counter with a sliding window to match character distributions