Sponsored
Sponsored
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.
1def In this Python solution, the array is sorted, then two slowly advancing pointers attempt to find unique pairs. The strategy handles tight comparisons, updating the left if necessary to avoid counting duplicates.