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.
1functionJavaScript's solution first sorts the array, letting two pointers sieve the array for pairs with k differences. With special handling of duplicates, the unique k-diff pairs are effectively derived.