K-diff Pairs in an Array

K-diff Pairs in an Array

1. What is this problem about?

The K-diff Pairs in an Array interview question asks you to find the number of unique pairs $(nums[i], nums[j])$ such that their absolute difference is exactly k. For example, in [3, 1, 4, 1, 5] with $k=2$, the pairs are $(1, 3)$ and $(3, 5)$. Note that the question asks for unique pairs, so $(1, 3)$ should only be counted once even if there are multiple 1s and 3s.

2. Why is this asked in interviews?

Companies like Apple and Microsoft ask this to evaluate a candidate's mastery of Hash Table interview patterns. It evaluates if you can handle edge cases like $k=0$ (finding duplicates) and if you can avoid $O(N^2)$ comparisons by using a frequency map. It’s a test of efficient search and deduplication.

3. Algorithmic pattern used

This problem is solved using a Frequency Map.

1. Count: Store the frequency of every number in a Hash Map.
2. Logic:
   • If $k > 0$: For each unique number $x$ in the map, check if $x + k$ also exists in the map.
   • If $k = 0$: For each unique number $x$, check if its frequency is $\geq 2$.
3. Deduplication: By iterating over the keys of the map, you naturally ensure each pair is only considered once.

4. Example explanation

Array: [1, 1, 1, 2, 2], $k = 0$.

• Map: {1: 3, 2: 2}.
• For 1: frequency is 3 ($\geq 2$). Count = 1.
• For 2: frequency is 2 ($\geq 2$). Count = 2. Result: 2. Array: [1, 3, 5], $k = 2$.
• For 1: $1+2=3$ exists. Count = 1.
• For 3: $3+2=5$ exists. Count = 2.
• For 5: $5+2=7$ doesn't exist. Result: 2.

5. Common mistakes candidates make

• Sorting and Two Pointers: This works ($O(N \log N)$), but you must be careful to skip duplicates to avoid over-counting.
• Absolute Value Confusion: Trying to check both $x+k$ and $x-k$ for every element, which leads to double-counting the same pair.
• Negative k: Not checking if $k$ is negative (distance cannot be negative).

6. Interview preparation tip

Whenever you need to find pairs with a specific difference, always think about the "Complement" rule: X - Y = K means X = Y + K. This transforms a search for a pair into a search for a single value in a map. This is a vital Hash Table interview pattern.