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 <unordered_map>
2#include <vector>
3
4int findPairs(std::vector<int>& nums, int k) {
5 std::unordered_map<int, int> freq_map;
6 int count = 0;
7 for (int num : nums) {
8 freq_map[num]++;
9 }
10 for (const auto& pair : freq_map) {
11 if (k == 0) {
12 if (pair.second > 1) count++;
13 } else if (freq_map.find(pair.first + k) != freq_map.end()) {
14 count++;
15 }
16 }
17 return count;
18}Using a C++ unordered_map as a frequency map, it calculates all possible k-diff pairs by iterating through the map. For k differences of zero, the pair's value must occur more than once.
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.