2 minutes
Leetcode 1769
Max Number of K-sum Pairs
Head on over here to try the problem for yourself.
This is a varaition of the famous two-sum problem that we have all struggled with 😅
Algorithm & Code
The slower O(n)
The goal is the count unique pairs of integers that sum up to given k
. For this, we create a hashmap that stores unique values of the integers. Then we go over the keySet()
and update the count according to the following rules:
- if
key = k/2
thencount += occurence(key)/2
- if map has
k - key
thencount += Min(occurence(key), occurence(k - key))
.
I keep track of the visited elements using a HashSet visited
. The case of key == k/2
is only raised when k, so I avoid any ugly conversions from double to Integer.
Slow code :(
public static int maxOperations(int nums[], int k) {
int count = 0;
HashMap<Integer, Integer> map = new HashMap<>();
HashSet<Integer> visited = new HashSet<>();
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(nums[i]))
map.put(nums[i], map.get(nums[i]) + 1);
else map.put(nums[i], 1);
}
for(Integer key : map.keySet()) {
System.out.printf("%d : %d\n", key, map.get(key));
}
for(Integer key : map.keySet()) {
if(visited.contains(key)) continue;
else {
if(k % 2 == 0 && key == k/2)
count += map.get(key)/2;
else if(map.containsKey(k - key))
count += Math.min(map.get(key), map.get(k - key));
visited.add(k - key);
}
}
return count;
}
As you can see, we explore the array first. Then we proceed with the counting. Fortunately, some very smart people in the comments came up with a way to do both simultaneously, with the use of HashMap.getOrDefault()
.
The faster O(n)
This code updates the count incrementally, rather than at once. As a result, it is able to populate the explored hashmap and count simultaneously. It checks if the pair of the element exists in the hashmap. On this basis it executes the following steps:
if((k-key) in map and occurence(k-key) > 0)
then remove an occurence and update count- else just add a new element or update its previous value
The faster code 😄
public int maxOperations(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
int count = 0;
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(k - nums[i]) && map.get(k - nums[i]) > 0) {
count++;
map.put(k - nums[i], map.get(k - nums[i]) - 1);
}
else {
// getOrDefault makes this part a lot less ugly 😄
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
}
return count;
}