Problem Description

Given an array of integers nums and an integer k, your task is to find the maximum number of unique pairs of elements in nums that add up to k. Each element in nums can be used at most once in a pair. The pairs are unordered (i.e., (a, b) is the same as (b, a)), and you should return the maximum number of such pairs you can form.

Constraints:

• Each number in nums can be used in at most one pair.
• The input array may contain duplicates and negative numbers.
• There may be multiple possible valid pairings; you only need to return the count.

Thought Process

At first glance, you might consider checking every possible pair of numbers to see if they add up to k. This brute-force approach would work, but it would be very slow for large arrays because you'd have to look at every possible pair.

Instead, we can look for a more efficient way. The key is to avoid reusing elements and to maximize the number of pairs. If we can quickly check for the "complement" (i.e., k - num) of each number, we could efficiently form pairs without checking every combination.

This suggests using a data structure that allows for fast lookups and updates, such as a hash map (or dictionary). By keeping track of how many times each number appears, we can efficiently pair numbers and ensure we don't reuse them.

Solution Approach

We use a hash map (dictionary) to count the occurrences of each number in nums. Here’s a step-by-step breakdown:

1. Count Elements: Traverse the array and count how many times each number appears. Store these counts in a hash map.
2. Pair Formation: For each unique number in the hash map:
   • Compute its complement as k - num.
   • If the complement exists in the hash map, form as many pairs as possible using the minimum count between the number and its complement.
   • Reduce the counts in the hash map accordingly so elements are not reused.
   • Special Case: If num is exactly half of k (i.e., num == k - num), you can only form count // 2 pairs from that number.
3. Return the Result: After processing, return the total number of pairs formed.

This approach ensures that each element is used at most once and that we maximize the number of pairs.

Example Walkthrough

Example Input: nums = [1, 2, 3, 4], k = 5

1. Count Elements: {1:1, 2:1, 3:1, 4:1}
2. Try Pairing:
   • For 1: complement is 4. Both exist, so form 1 pair (1,4), reduce their counts.
   • For 2: complement is 3. Both exist, so form 1 pair (2,3), reduce their counts.
   • For 3 and 4: counts are now 0, so no more pairs.
3. Total pairs formed: 2 ([1,4] and [2,3])

Time and Space Complexity

• Brute-Force Approach:
  • Time Complexity: O(n^2) because you would check every pair.
  • Space Complexity: O(1) (not counting input storage).
• Optimized Hash Map Approach:
  • Time Complexity: O(n) because you traverse the array a few times (to count and to pair).
  • Space Complexity: O(n) for the hash map storing counts.

Summary

The key insight is to use a hash map to efficiently track and pair numbers whose sum equals k, ensuring each element is used at most once. This optimized approach is both elegant and efficient, reducing the time from quadratic to linear, and making the solution practical for large inputs. By counting occurrences and smartly pairing, we maximize the number of valid k-sum pairs.

Code Implementation

from collections import Counter

class Solution:
    def maxOperations(self, nums, k):
        count = Counter(nums)
        res = 0
        for num in count:
            complement = k - num
            if complement in count:
                if num == complement:
                    pairs = count[num] // 2
                else:
                    pairs = min(count[num], count[complement])
                res += pairs
                # Remove used elements to avoid reuse
                count[num] -= pairs
                count[complement] -= pairs
        return res
      

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int maxOperations(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        int res = 0;
        for (auto& [num, cnt] : count) {
            int complement = k - num;
            if (count.find(complement) != count.end()) {
                if (num == complement) {
                    int pairs = cnt / 2;
                    res += pairs;
                    count[num] -= pairs * 2;
                } else {
                    int pairs = min(count[num], count[complement]);
                    res += pairs;
                    count[num] -= pairs;
                    count[complement] -= pairs;
                }
            }
        }
        return res;
    }
};
      

import java.util.HashMap;

class Solution {
    public int maxOperations(int[] nums, int k) {
        HashMap<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        int res = 0;
        for (int num : count.keySet()) {
            int complement = k - num;
            if (count.containsKey(complement)) {
                if (num == complement) {
                    int pairs = count.get(num) / 2;
                    res += pairs;
                    count.put(num, count.get(num) - pairs * 2);
                } else {
                    int pairs = Math.min(count.get(num), count.get(complement));
                    res += pairs;
                    count.put(num, count.get(num) - pairs);
                    count.put(complement, count.get(complement) - pairs);
                }
            }
        }
        return res;
    }
}
      

var maxOperations = function(nums, k) {
    const count = new Map();
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    let res = 0;
    for (const [num, cnt] of count.entries()) {
        const complement = k - num;
        if (count.has(complement)) {
            if (num === complement) {
                const pairs = Math.floor(count.get(num) / 2);
                res += pairs;
                count.set(num, count.get(num) - pairs * 2);
            } else {
                const pairs = Math.min(count.get(num), count.get(complement));
                res += pairs;
                count.set(num, count.get(num) - pairs);
                count.set(complement, count.get(complement) - pairs);
            }
        }
    }
    return res;
};