K-diff Pairs in an Array
Problem
Return the number of unique k-diff pairs (i, j) where |nums[i] − nums[j]| == k. Pairs are unique by value; k ≥ 0.
nums = [3, 1, 4, 1, 5], k = 22from collections import Counter
def find_pairs(nums, k):
cnt = Counter(nums)
if k == 0:
return sum(1 for v in cnt.values() if v >= 2)
return sum(1 for x in cnt if x + k in cnt)function findPairs(nums, k) {
const cnt = new Map();
for (const x of nums) cnt.set(x, (cnt.get(x) || 0) + 1);
let pairs = 0;
if (k === 0) {
for (const v of cnt.values()) if (v >= 2) pairs++;
} else {
for (const x of cnt.keys()) if (cnt.has(x + k)) pairs++;
}
return pairs;
}class Solution {
public int findPairs(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) cnt.merge(x, 1, Integer::sum);
int pairs = 0;
if (k == 0) {
for (int v : cnt.values()) if (v >= 2) pairs++;
} else {
for (int x : cnt.keySet()) if (cnt.containsKey(x + k)) pairs++;
}
return pairs;
}
}int findPairs(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
for (int x : nums) cnt[x]++;
int pairs = 0;
if (k == 0) {
for (auto& [v, c] : cnt) if (c >= 2) pairs++;
} else {
for (auto& [v, c] : cnt) if (cnt.count(v + k)) pairs++;
}
return pairs;
}Explanation
We want to count distinct value pairs whose difference is exactly k. Building a frequency map first with Counter(nums) lets us reason about unique values instead of indices, which automatically handles the "unique by value" requirement.
There are two cases. When k == 0, a valid pair needs two copies of the same number, so we count values whose frequency is >= 2.
When k > 0, a value x forms a pair with x + k. We count each distinct key x for which x + k also exists in the map. Looking only "upward" at x + k guarantees we never count the same pair twice.
Example: nums = [3, 1, 4, 1, 5], k = 2. Distinct values are 1, 3, 4, 5. Checking x + 2: 1+2=3 exists, 3+2=5 exists, 4+2=6 absent, 5+2=7 absent. That gives 2 pairs: (1,3) and (3,5).
Because each value is examined once with O(1) map lookups, the whole count is linear in the array size.