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.
1import
Java implementation employs sorting of the array, post which two pointers aid in identifying unique pairs. Handling of duplicates ensures only unique pairs are counted.