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