Count Number of Pairs With Absolute Difference K

Count Number of Pairs With Absolute Difference K

What is this problem about?

In the "Count Number of Pairs With Absolute Difference K" coding problem, you are given an integer array and a value $k$. You need to find the number of pairs $(i, j)$ such that $i < j$ and $|nums[i] - nums[j]| == k$. This is a basic search and count problem that focuses on efficiency and frequency tracking.

Why is this asked in interviews?

This "Easy" difficulty question is common in initial screening rounds at Goldman Sachs and Oracle. It tests whether a candidate can optimize a simple search. While a nested loop ($O(n^2)$) works, interviewers look for a linear time solution ($O(n)$) using a Hash Map, which demonstrates an understanding of time-space trade-offs.

Algorithmic pattern used

The pattern used is Frequency Counting with a Hash Table.

1. Create a frequency map of all numbers in the array.
2. Iterate through the unique keys in the map.
3. For each number $x$, check if $x + k$ also exists in the map.
4. If it does, the number of pairs formed by these two values is count(x) * count(x + k).
5. Sum these products for all $x$.

Example explanation

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

• Frequency Map: {1: 2, 2: 2}.
• Check $x=1$: Is $1+1=2$ in map? Yes. Pairs = $2 imes 2 = 4$.
• Check $x=2$: Is $2+1=3$ in map? No. Total count: 4. The pairs are (index 0,1), (0,2), (1,3), (2,3).

Common mistakes candidates make

A common error is double-counting pairs (e.g., checking both $x+k$ and $x-k$ for every element). Another mistake is miscalculating the number of pairs when $k=0$ (though $k$ is usually positive in this problem). Some candidates also struggle with the $i < j$ constraint, although with a frequency map, the ordering is implicitly handled by only checking in one direction ($x+k$).

Interview preparation tip

For any "pair" problem involving a difference or sum, always ask yourself: "Can I find the 'complement' element in $O(1)$ time?" If the answer is yes, a Hash Map is your primary tool.