## 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` then `count += occurence(key)/2`
• if map has `k - key` then `count += 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));
}
}

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;
}
``````