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.
1from collections import Counter
2
3def findPairs(nums, k):
4 count = 0
5 freq = Counter(nums)
6 for num in freq:
7 if k == 0:
8 if freq[num] > 1:
9 count += 1
10 else:
11 if num + k in freq:
12 count += 1
13 return countThis 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.
1defIn 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.