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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int FindPairs(int[] nums, int k) {
6 Dictionary<int, int> map = new Dictionary<int, int>();
7 int count = 0;
8 foreach (var num in nums) {
9 if (map.ContainsKey(num)) map[num]++;
10 else map[num] = 1;
11 }
12 foreach (var kvp in map) {
13 if (k == 0) {
14 if (kvp.Value > 1) count++;
} else {
if (map.ContainsKey(kvp.Key + k)) count++;
}
}
return count;
}
}C# utilizes a Dictionary for counting the frequency of elements. It then searches for pairs by checking the dictionary keys with the difference considered.
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.
1using System;
public class Solution {
public int FindPairs(int[] nums, int k) {
Array.Sort(nums);
int count = 0, left = 0, right = 0;
while (right < nums.Length) {
if (right == left || nums[right] - nums[left] < k) {
right++;
} else if (nums[right] - nums[left] > k) {
left++;
} else {
count++;
left++;
while (right < nums.Length - 1 && nums[right] == nums[right + 1]) right++;
right++;
}
}
return count;
}
}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.
In C#, the method involves sorting and manipulating pointers. When duplicates appear, they are skipped to assure pairs are distinctly counted. Sorting aids timely checks.