Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.
A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:
0 <= i, j < nums.lengthi != j|nums[i] - nums[j]| == kNotice that |val| denotes the absolute value of val.
Example 1:
Input: nums = [3,1,4,1,5], k = 2 Output: 2 Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5). Although we have two 1s in the input, we should only return the number of unique pairs.
Example 2:
Input: nums = [1,2,3,4,5], k = 1 Output: 4 Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
Example 3:
Input: nums = [1,3,1,5,4], k = 0 Output: 1 Explanation: There is one 0-diff pair in the array, (1, 1).
Constraints:
1 <= nums.length <= 104-107 <= nums[i] <= 1070 <= k <= 107In #532 K-diff Pairs in an Array, the goal is to count unique pairs (i, j) such that the absolute difference between the numbers is k. A common strategy is to use a hash set or hash map to track numbers while scanning the array. For each element, you check whether its complementary value num + k or num - k has appeared, ensuring pairs are counted only once.
Another efficient method is to sort the array and apply the two-pointer technique. After sorting, move two pointers through the array and compare their difference with k. Adjust the pointers depending on whether the difference is smaller or larger than k, while skipping duplicates to ensure unique pairs.
A variation using binary search can also work: sort the array and search for num + k for each element. Among these, the sorting with two pointers or hash-based approach typically offers the best balance between simplicity and performance.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map / Hash Set | O(n) | O(n) |
| Sorting + Two Pointers | O(n log n) | O(1) to O(n) depending on sorting |
| Sorting + Binary Search | O(n log n) | O(1) |
NeetCodeIO
This approach uses a HashMap to track the frequency of each element in the array. For each unique element, we will check if there's another element that can form a k-diff pair with it. When k is zero, we need to check if there are duplicates present in the list.
Time Complexity: O(n) because we iterate over the array and then over the hashmap that is bounded by a constant size. Space Complexity: O(n) to store the frequency map.
1from collections import Counter
2
3def findPairs(nums, k):
4 count = 0
5 freq = Counter(nums)
6 for num This Python code uses a Counter to handle frequency counting. It correctly differentiates between the k=0 special case and positive k values, iterating over the elements in the frequency dictionary.
This approach involves sorting the array initially, then using two pointers to determine unique k-diff pairs. The array being sorted helps us efficiently reduce potential pair checks, and ensure pairs are considered only once.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) if disregard input.
1import
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem reflects common interview patterns involving arrays, hashing, and two-pointer techniques. Variations of difference-based pair problems frequently appear in technical interviews at companies like Amazon, Google, and Meta. Practicing it helps strengthen pattern recognition for similar questions.
The optimal approach often uses a hash set or hash map to track elements and check whether a complementary value exists for a given number. This allows counting unique pairs efficiently in linear time. It avoids nested loops and handles duplicates carefully.
Yes, after sorting the array you can apply the two-pointer technique to compare the difference between two elements. By adjusting the pointers based on whether the difference is smaller or larger than k, you can find valid pairs efficiently. You also need to skip duplicates to ensure pairs are unique.
A hash set or hash map is typically the best data structure because it provides constant-time lookups. It allows you to quickly check whether the required difference value already exists in the array. This makes the algorithm efficient for large inputs.
Java implementation employs sorting of the array, post which two pointers aid in identifying unique pairs. Handling of duplicates ensures only unique pairs are counted.