Leetcode 1679: Max Number of K-Sum Pairs

In this Leetcode problem, we are given an array nums of integers. In one operation, we can take any pair of integers adding up to k and take it out of the array. We want to know the maximum number of operations that we can do following that rule.

For any number num in nums, it can only be paired with k — numfor the sum to be equal tok. Then, for any number 1 ≤ p ≤ k — 1, if we have the value p repeated x times in nums, and the value k — p repeated y times, we can form min(x,y) pairs using these 2 values, unless p and k — p are the same.

If k is pair, if the value k/2 is repeated x times in nums, we can only make x/2 pairs using these values. If we ignore this, and apply the same previous formula, min(x, x), we will count twice as many pairs as needed.

However, we can notice that if we count the pair (p, k — p), and later on count the pair (k — p, p), we also will double the number of operations.

Therefore, in the algorithms, we will count all operations twice, by ignoring the special case of k/2, and by counting the pairs (p, k - p) and (k — p, p). We will only need to divide the result by 2 at the end.

To solve the problem, we count the number of occurrences of each 1 ≤ p < k, in a map count. Then for each key in the map we add
min(count.get(key), count.get(k — key))
to the final result. As explained before, doing this will exactly double the expected final result.

Here is the full Java solution:

class Solution {
    public int maxOperations(int[] nums, int k) {
        if (k == 1) {
            return 0;
        }
        Map<Integer, Integer> count = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int v = nums[i];
            if (v < k) {
                count.put(v, count.getOrDefault(v, 0) + 1);
            }
        }
        int res = 0;
        for (int key : count.keySet()) {
            res += Math.min(
                count.getOrDefault(key, 0),
                count.getOrDefault(k - key, 0));
        }
        return res / 2;  
    }
}