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.
1import java.util.HashMap;
2
3public class Solution {
4 public int findPairs(int[] nums, int k) {
5 HashMap<Integer, Integer> map = new HashMap<>();
6 int count = 0;
7 for (int num : nums) {
8 map.put(num, map.getOrDefault(num, 0) + 1);
9 }
10 for (int key : map.keySet()) {
11 if (k == 0) {
12 if (map.get(key) >= 2) count++;
13 } else if (map.containsKey(key + k)) {
14 count++;
15 }
16 }
17 return count;
18 }
19}In Java, the solution uses a HashMap to count occurrences of each element. It then iterates over the keys to see if valid k-diff pairs exist.
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.