LeetCode 1679 - Max Number of K-Sum Pairs
The problem asks us to repeatedly remove pairs of numbers from an array such that the sum of each selected pair equals a
Difficulty: 🟡 Medium
Topics: Array, Hash Table, Two Pointers, Sorting
Solution
Problem Understanding
The problem asks us to repeatedly remove pairs of numbers from an array such that the sum of each selected pair equals a target value k. Every time we successfully remove one valid pair, it counts as one operation. Our goal is to determine the maximum number of operations that can be performed before no more valid pairs remain.
In simpler terms, we want to find how many disjoint pairs can be formed where:
num1 + num2 = k
Each element in the array can only be used once because once a pair is selected, both numbers are removed from the array. This means we must be careful not to reuse values accidentally.
The input consists of:
nums, an integer array containing values we can pair together.k, the target sum that every valid pair must equal.
The expected output is a single integer representing the maximum number of pair-removal operations possible.
The constraints are important:
nums.length <= 10^5nums[i] <= 10^9k <= 10^9
Since the array can contain up to one hundred thousand elements, an inefficient nested-loop solution will not scale well. The large value range for nums[i] also suggests that counting with a fixed-size array is impractical. Instead, we need a method that efficiently tracks previously seen numbers, which makes a hash map an excellent candidate.
Several edge cases are worth identifying early. The array may contain no valid pairs at all, in which case the answer is 0. There may be repeated values, such as multiple identical numbers contributing to different valid pairs. Cases where a number pairs with itself, such as k = 6 and two occurrences of 3, require careful counting so we do not reuse the same element twice. The problem guarantees that the input is non-empty and contains positive integers, so we do not need to handle invalid input or negative lengths.
Approaches
Brute Force Approach
A straightforward solution is to repeatedly search for valid pairs by checking every possible combination of numbers.
For each element, we could scan the rest of the array looking for another element whose sum equals k. Once a pair is found, we remove both numbers and continue searching among the remaining elements.
This approach is correct because it explicitly checks every possible pair and removes valid matches one at a time. Eventually, no valid pair remains, and the total number of removals gives the answer.
However, this method is inefficient. In the worst case, we compare nearly every pair of elements, leading to quadratic time complexity. With 10^5 elements, an O(n²) algorithm becomes too slow.
Optimal Approach, Hash Map for Complements
The key observation is that for any number x, the only value that can form a valid pair is:
k - x
Instead of repeatedly searching the entire array, we can maintain a hash map that stores how many unmatched numbers we have seen so far.
As we iterate through the array:
- For the current number
num, calculate its complementk - num. - If the complement already exists in our hash map, we form a pair immediately and reduce the stored frequency.
- Otherwise, we store the current number for possible future matching.
This works because every element is processed exactly once, and each valid pair is greedily formed as soon as possible.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Checks all possible pairs repeatedly |
| Optimal | O(n) | O(n) | Uses a hash map to track unmatched complements |
Algorithm Walkthrough
- Create a hash map called
frequencyto track unmatched numbers we have encountered. - Initialize a variable
operations = 0to count successful pair removals. - Iterate through each number
numinnums. - For the current number, compute the complement:
complement = k - num
This is the only number that can form a valid pair with num.
5. Check whether the complement exists in the hash map and has a positive count.
- If it exists, we have found a valid pair.
- Increment
operations. - Decrease the complement count because one occurrence has now been used.
- If no complement exists, store the current number in the hash map by increasing its frequency count.
- Continue until all elements are processed.
- Return
operations.
The reason we use a hash map is that it provides average O(1) lookup and insertion time. Instead of scanning the array repeatedly for matching values, we immediately know whether a complement is available.
Why it works
The algorithm maintains an important invariant: the hash map only contains unmatched numbers that have been seen so far.
Whenever we encounter a number, we first try to match it with an earlier unmatched complement. If a complement exists, forming the pair immediately is always optimal because delaying the match cannot produce more pairs later. Since every number participates in at most one pair, greedily matching valid complements guarantees the maximum number of operations.
Python Solution
from typing import List
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
frequency = {}
operations = 0
for num in nums:
complement = k - num
if frequency.get(complement, 0) > 0:
operations += 1
frequency[complement] -= 1
else:
frequency[num] = frequency.get(num, 0) + 1
return operations
The implementation follows the algorithm directly.
We begin by creating a dictionary named frequency. This dictionary stores numbers that have appeared but have not yet been paired. The key is the number itself, and the value is how many unmatched copies currently exist.
For each number in nums, we compute the complement using k - num. We then check whether that complement already exists in the dictionary.
If it exists with a positive count, we immediately form a pair. We increment the operation counter and reduce the stored complement count because one instance has now been consumed.
If the complement does not exist, we store the current number in the dictionary for future matching.
At the end of the traversal, the operation counter contains the maximum number of valid pair removals.
Go Solution
func maxOperations(nums []int, k int) int {
frequency := make(map[int]int)
operations := 0
for _, num := range nums {
complement := k - num
if frequency[complement] > 0 {
operations++
frequency[complement]--
} else {
frequency[num]++
}
}
return operations
}
The Go implementation is almost identical to the Python version.
Instead of a Python dictionary, we use a map[int]int to store frequencies of unmatched numbers. Go maps return the zero value for missing keys, which simplifies the complement check because frequency[complement] automatically evaluates to 0 when absent.
There are no special concerns around integer overflow because the constraints fit comfortably within Go's int type. Empty and nil slices are handled naturally by the loop, although the problem guarantees at least one element.
Worked Examples
Example 1
Input:
nums = [1,2,3,4], k = 5
| Step | Current Number | Complement | Hash Map State | Operations |
|---|---|---|---|---|
| 1 | 1 | 4 | {1:1} | 0 |
| 2 | 2 | 3 | {1:1, 2:1} | 0 |
| 3 | 3 | 2 | {1:1, 2:0} | 1 |
| 4 | 4 | 1 | {1:0, 2:0} | 2 |
At step 3, the number 3 finds complement 2, so we form a pair (2,3).
At step 4, the number 4 finds complement 1, so we form another pair (1,4).
Final answer:
2
Example 2
Input:
nums = [3,1,3,4,3], k = 6
| Step | Current Number | Complement | Hash Map State | Operations |
|---|---|---|---|---|
| 1 | 3 | 3 | {3:1} | 0 |
| 2 | 1 | 5 | {3:1, 1:1} | 0 |
| 3 | 3 | 3 | {3:0, 1:1} | 1 |
| 4 | 4 | 2 | {3:0, 1:1, 4:1} | 1 |
| 5 | 3 | 3 | {3:1, 1:1, 4:1} | 1 |
At step 3, the second 3 matches the first 3 because:
3 + 3 = 6
The last 3 has no unmatched partner remaining.
Final answer:
1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each element is processed once with O(1) average hash map operations |
| Space | O(n) | In the worst case, all elements remain unmatched and are stored |
The time complexity is linear because we iterate through the array only once. Every hash map lookup and update is an average O(1) operation.
The space complexity is O(n) in the worst case when no valid pairs exist and every element must be stored in the hash map.
Test Cases
solution = Solution()
assert solution.maxOperations([1, 2, 3, 4], 5) == 2 # Example 1
assert solution.maxOperations([3, 1, 3, 4, 3], 6) == 1 # Example 2
assert solution.maxOperations([1], 2) == 0 # Single element, impossible to pair
assert solution.maxOperations([1, 1, 1, 1], 2) == 2 # Multiple identical pairs
assert solution.maxOperations([3, 3, 3, 3], 6) == 2 # Self-pairing numbers
assert solution.maxOperations([1, 2, 3], 10) == 0 # No valid pairs
assert solution.maxOperations([2, 2, 2, 2, 2], 4) == 2 # Odd count of pairable numbers
assert solution.maxOperations([1, 5, 1, 5], 6) == 2 # Multiple repeated complements
assert solution.maxOperations([1, 2, 3, 4, 5, 6], 7) == 3 # Every number pairs
assert solution.maxOperations([10**9, 1, 10**9 - 1], 10**9) == 1 # Large values
| Test | Why |
|---|---|
[1,2,3,4], k=5 |
Validates the first provided example |
[3,1,3,4,3], k=6 |
Validates duplicate handling from the second example |
[1], k=2 |
Tests minimum array size |
[1,1,1,1], k=2 |
Verifies repeated identical pairs |
[3,3,3,3], k=6 |
Ensures self-pairing logic works |
[1,2,3], k=10 |
Validates behavior when no pairs exist |
[2,2,2,2,2], k=4 |
Tests odd-frequency leftovers |
[1,5,1,5], k=6 |
Confirms repeated complement matching |
[1,2,3,4,5,6], k=7 |
Verifies multiple disjoint pair formation |
| Large-value input | Ensures large integers are handled correctly |
Edge Cases
Arrays With No Valid Pairs
An important case occurs when no two numbers sum to k, such as:
nums = [1,2,3], k = 10
A buggy implementation might accidentally count partial matches or assume every number contributes to a pair. Our implementation handles this safely because unmatched numbers simply accumulate in the hash map, and the operation count remains 0.
Numbers That Pair With Themselves
When num * 2 == k, a number must pair with another identical value. For example:
nums = [3,3,3], k = 6
Only one pair is possible because one 3 remains unused. This case can easily introduce bugs if the algorithm reuses the same occurrence twice. Our frequency map avoids this problem by decrementing counts whenever a match is consumed.
Odd Number of Matching Values
Consider:
nums = [2,2,2,2,2], k = 4
Even though every value can theoretically pair, an odd count leaves one unmatched element. The correct answer is 2, not 2.5 or 3. Since the algorithm removes exactly one complement for each successful match, leftover unmatched values remain correctly unused.
Large Inputs With Many Duplicates
With arrays approaching 10^5 elements, a nested-loop approach becomes prohibitively slow. For example, an input containing thousands of repeated numbers would cause quadratic behavior in a brute-force implementation. The hash map approach still processes every element once, ensuring the solution remains efficient at scale.