K-diff Pairs in an Array — Solution in Python, Java & C++
K-diff Pairs in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
K-diff Pairs in an Array is a medium coding problem on arrays and hash table, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums and an integer k, return the number of unique k-diff pairs in the array.
A k-diff pair is a pair (nums[i], nums[j]) with i != j and |nums[i] - nums[j]| == k. Two pairs are the same if they consist of the same two values, so (1,3) and (3,1) count once.
Example 1
Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: The pairs are (1,3) and (3,5). The duplicate 1 does not create a third pair.
Example 2
Input: nums = [1,2,3,4,5], k = 1
Output: 4
Explanation: (1,2), (2,3), (3,4) and (4,5).
Example 3
Input: nums = [1,3,1,5,4], k = 0
Output: 1
Explanation: Only the value 1 appears more than once.
Constraints
1 <= nums.length <= 10000-10000000 <= nums[i] <= 100000000 <= k <= 10000000
Hints for K-diff Pairs in an Array
Hint 1
"Unique pairs" means you should be counting values, not index pairs.
Hint 2
Build a frequency map, then iterate over its distinct keys.
Hint 3
k == 0is a special case: the pair is a value paired with itself, so it needs a frequency of at least 2.
How to solve K-diff Pairs in an Array
Because pairs are identified by their values, collapse the array to a frequency map first. Then each distinct value x contributes at most one pair — the one with x + k.
Approach
- Count occurrences of every value into a map.
- For each distinct key
x: ifk == 0, add 1 whencount[x] > 1. - If
k > 0, add 1 whenx + kis also a key. - Return the running total.
Why it works
Fixing the smaller element of the pair as x and looking only upward to x + k visits every unordered value pair exactly once, which is precisely the uniqueness rule the problem states.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Checking both
x + kandx - kdouble-counts every pair. - Forgetting
k == 0makes duplicate values report a pair for every occurrence. - Sorting plus two pointers also works but must skip equal values explicitly.
Reference solution
Python
from typing import List
def findPairs(nums: List[int], k: int) -> int:
if k < 0:
return 0
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1
total = 0
for x in count:
if k == 0:
if count[x] > 1:
total += 1
elif x + k in count:
total += 1
return totalJava
public static int findPairs(int[] nums, int k) {
if (k < 0) return 0;
HashMap<Integer, Integer> count = new HashMap<>();
for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
int total = 0;
for (Map.Entry<Integer, Integer> e : count.entrySet()) {
if (k == 0) {
if (e.getValue() > 1) total++;
} else if (count.containsKey(e.getKey() + k)) {
total++;
}
}
return total;
}C++
int findPairs(vector<int>& nums, int k) {
if (k < 0) return 0;
unordered_map<int, int> count;
for (int x : nums) count[x]++;
int total = 0;
for (auto& e : count) {
if (k == 0) {
if (e.second > 1) total++;
} else if (count.find(e.first + k) != count.end()) {
total++;
}
}
return total;
}JavaScript
var findPairs = function(nums, k) {
if (k < 0) return 0;
const count = {};
for (let i = 0; i < nums.length; i++) {
const key = String(nums[i]);
count[key] = (count[key] || 0) + 1;
}
let total = 0;
const keys = Object.keys(count);
for (let i = 0; i < keys.length; i++) {
const x = Number(keys[i]);
if (k === 0) {
if (count[keys[i]] > 1) total++;
} else if (count[String(x + k)] !== undefined) {
total++;
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets