Problem Overview
LeetCode 1679 Max Number of K-Sum Pairs gives you an integer array nums and an integer k. In one operation you pick two elements from the array that sum to k and remove them. Your goal is to find the maximum number of such operations you can perform.
Each element can be used in at most one operation — once a pair is removed those two elements are gone. The problem asks for the maximum count of valid removals, not the actual pairs themselves. This makes it a counting problem rather than a search problem.
The problem is rated Medium and appears frequently in interviews at companies like Google and Amazon. The key insight is that it extends the classic Two Sum problem from "find one pair" to "count all disjoint pairs," which shifts the solution from a single-pass hash lookup to a frequency-map approach.
- Given integer array nums and integer k, find max removal operations
- Each operation: pick two elements summing to k, remove both
- Each element participates in at most one operation
- Return the maximum number of operations possible
- Constraints: 1 to 10^5 elements, values in [1, 10^9], 2 ≤ k ≤ 10^9
HashMap Complement Counting
The O(n) hashmap approach iterates through the array once. For each element num, compute its complement as k minus num. If the complement's count in the frequency map is greater than zero, a valid pair exists — increment the operations counter and decrement the complement's count in the map. Otherwise, increment num's count in the map.
This single pass works because whenever you encounter a number whose complement is already recorded, you can immediately pair them and consume one instance of the complement. The map effectively tracks "unpaired" elements waiting for their complement to appear later in the array.
The algorithm never double-counts because decrementing the complement's frequency immediately removes that instance from future pairing. After the full pass, the map contains only elements that could not be paired with any complement in the array.
Two Sum Extended
This is Two Sum extended to counting all pairs instead of finding one. The complement lookup pattern is identical — complement = k - num — but instead of returning indices you increment a counter and decrement the complement's frequency. The map stores unpaired elements, not all elements.
HashMap Implementation
The implementation is a tight loop over the array. Maintain a dictionary (or HashMap) called count. For each num in nums: compute complement = k - num. If count[complement] > 0, you have a match — increment operations by 1 and decrement count[complement] by 1. Otherwise, increment count[num] by 1.
In Python this is naturally expressed with collections.Counter or a defaultdict(int). In Java use a HashMap<Integer, Integer> with getOrDefault for safe reads. The defaultdict approach avoids explicit key existence checks and keeps the code concise.
After the loop, return operations. The total time is O(n) for the single pass and O(n) space for the frequency map in the worst case (no pairs found, every element stored). In practice the map is smaller when many pairs exist.
- 1Initialize count = {} and operations = 0
- 2For each num in nums: compute complement = k - num
- 3If count[complement] > 0: operations += 1, count[complement] -= 1
- 4Else: count[num] += 1 (store num for future pairing)
- 5Return operations after the full pass
Sort + Two Pointers Alternative
An alternative approach sorts the array first and then applies two pointers. Set left = 0 and right = n - 1. While left < right: compute the current sum as nums[left] + nums[right]. If the sum equals k, increment operations, move left up by one, and move right down by one. If the sum is less than k, move left up to increase the sum. If the sum is greater than k, move right down to decrease the sum.
The two-pointer approach works on sorted arrays because sorting guarantees that moving left right increases the sum and moving right left decreases it. This deterministic navigation ensures every valid pair is found without missing any or double-counting.
The overall complexity is O(n log n) dominated by the sort step, and O(1) extra space if sorting is done in-place (Python's sort and Java's Arrays.sort both sort in-place for primitive types). This is a worthwhile trade-off when memory is tightly constrained.
Time vs Space Trade-off
The two-pointer approach is O(n log n) vs O(n) for the hashmap, but it uses O(1) extra space if sorting in-place, while the hashmap uses O(n) space. For very large arrays where memory is constrained, the sort + two-pointer approach can be preferable despite the slower asymptotic time.
Walk-Through Example
Take nums = [1, 2, 3, 4] and k = 5. Using the hashmap approach: iterate left to right. Element 1: complement = 5 - 1 = 4, count[4] = 0, so store count[1] = 1. Element 2: complement = 5 - 2 = 3, count[3] = 0, so store count[2] = 1. Element 3: complement = 5 - 3 = 2, count[2] = 1 > 0, so operations = 1, count[2] = 0. Element 4: complement = 5 - 4 = 1, count[1] = 1 > 0, so operations = 2, count[1] = 0. Final result: 2 operations.
The two-pointer verification: sorted array [1, 2, 3, 4]. left=0, right=3: sum = 1+4 = 5 = k, operations=1, left=1, right=2. left=1, right=2: sum = 2+3 = 5 = k, operations=2, left=2, right=1. left >= right, stop. Result: 2.
Edge case: nums = [3, 1, 3, 4, 3] and k = 6. Hashmap: 3→comp=3, count[3]=0 → store count[3]=1. 1→comp=5, store count[1]=1. 3→comp=3, count[3]=1>0 → ops=1, count[3]=0. 4→comp=2, store. 3→comp=3, count[3]=0 → store count[3]=1. Result: 1 operation (the pair [3,3]).
- 1nums=[1,2,3,4], k=5 — HashMap approach
- 21: complement=4, not seen → store count[1]=1
- 32: complement=3, not seen → store count[2]=1
- 43: complement=2, found! ops=1, count[2]=0
- 54: complement=1, found! ops=2, count[1]=0 → result=2
Code Walkthrough: Python and Java
Python hashmap version using Counter: from collections import defaultdict; def maxOperations(nums, k): count = defaultdict(int); ops = 0; for num in nums: comp = k - num; if count[comp] > 0: ops += 1; count[comp] -= 1; else: count[num] += 1; return ops. Time O(n), space O(n). Python also supports a Counter pre-build: count = Counter(nums), then pair greedily — but the single-pass approach above avoids double-counting edge cases.
Python two-pointer version: def maxOperations(nums, k): nums.sort(); left, right = 0, len(nums)-1; ops = 0; while left < right: s = nums[left]+nums[right]; if s == k: ops+=1; left+=1; right-=1; elif s < k: left+=1; else: right-=1; return ops. Time O(n log n), space O(1).
Java HashMap version: public int maxOperations(int[] nums, int k) { Map<Integer,Integer> count = new HashMap<>(); int ops = 0; for (int num : nums) { int comp = k - num; if (count.getOrDefault(comp, 0) > 0) { ops++; count.put(comp, count.get(comp) - 1); } else { count.merge(num, 1, Integer::sum); } } return ops; }. Java two-pointer: Arrays.sort(nums); then the same left/right pointer loop.
Decrement, Do Not Delete
After pairing, decrement the complement's count — do not delete the key entirely. The same value might pair with another element later. For example, nums=[3,3,3,3] with k=6: the first 3 stores count[3]=1; the second 3 finds count[3]=1, ops=1, count[3]=0; the third 3 stores count[3]=1 again; the fourth 3 finds it, ops=2. Deleting instead of decrementing would break this.