402. K-diff Pairs in an Array
You receive an array of integers nums and a non-negative integer k. A k-diff pair is an unordered pair of values (a, b) such that both values occur in the array (at different positions) and |a − b| = k.
Return the number of distinct k-diff pairs. Pairs are counted by value, not by position: however many times the values 1 and 3 appear, (1, 3) counts once. When k = 0, a pair requires the same value at two different positions, so it counts exactly the values that occur more than once.
Example 1:
Input: nums = [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: The distinct pairs 2 apart are (1, 3) and (3, 5). Even though 1 appears twice, (1, 3) is still a single pair.
Example 2:
Input: nums = [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: With k = 0 a pair needs a repeated value. Only 1 occurs more than once, giving the single pair (1, 1).
Constraints:
- 1 ≤ nums.length ≤ 10⁴
- -10⁷ ≤ nums[i] ≤ 10⁷
- 0 ≤ k ≤ 10⁷
Hints:
Because pairs are counted by value, the multiset of positions barely matters — what you need to know is which values exist, and (for k = 0) which values repeat. What structure answers "does value v exist?" in O(1)?
Build a frequency map once. For k > 0, count the keys x whose partner x + k is also a key — checking only the +k direction counts each unordered pair exactly once. For k = 0, count the keys with frequency at least 2. Handle k = 0 separately or every value pairs with itself.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, 1, 4, 1, 5], k = 2
Expected output: 2