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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5int findPairs(int* nums, int numsSize, int k) {
6 int *hashMap = (int*)calloc(20001, sizeof(int));
7 int count = 0;
8 for(int i = 0; i < numsSize; i++) {
9 hashMap[nums[i] + 10000]++;
10 }
11 for(int i = 0; i < 20001; i++) {
12 if(hashMap[i]) {
13 int num = i - 10000;
14 if(k == 0) {
15 if(hashMap[i] >= 2) count++;
16 } else if(k > 0 && num + k <= 10000 && hashMap[num + k + 10000]) {
17 count++;
18 }
19 }
20 }
21 free(hashMap);
22 return count;
23}The code uses a frequency map stored as an array from -10000 to 10000 to count occurrences of each number. For a k-difference, if k is zero, we count pairs from duplicates. Otherwise, we look for the presence of the number plus k.
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.
1#
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.
After sorting, two pointers start from the beginning. We adjust pointers depending on the difference relative to k. Duplicates are handled by skipping same values.