K-diff Pairs in an Array
Medium · Two Pointers · Explanation and code example
Value-to-Index Map and One-Time Pair Counting
How it works
Map each distinct value to one of its indices. For a value x, a pair exists when x + k is present at another index. After counting it, remove that target entry so later duplicates cannot count the same value pair again.
Steps
- Build a value-to-index map.
- For each original index, look up value + k and ensure it uses another index.
- Count the pair and remove the target value from the map.
Complexity
- Time: O(n) expected with hashing.
- Space: O(n).
Things to watch for
- Count distinct value pairs, rather than every index pair.
- When k = 0, require at least two occurrences.
- Removing targets prevents duplicate counts.
Python code example
class Solution:
def findPairs(self, nums: list[int], k: int) -> int:
ans = 0
numToIndex = {num: i for i, num in enumerate(nums)}
for i, num in enumerate(nums):
target = num + k
if target in numToIndex and numToIndex[target] != i:
ans += 1
del numToIndex[target]
return ans
C++ code example
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
int ans = 0;
unordered_map<int, int> numToIndex;
for (int i = 0; i < nums.size(); ++i)
numToIndex[nums[i]] = i;
for (int i = 0; i < nums.size(); ++i) {
const int target = nums[i] + k;
if (const auto it = numToIndex.find(target);
it != numToIndex.cend() && it->second != i) {
++ans;
numToIndex.erase(target);
}
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.