Learn how to solve LeetCode Max Number of K-Sum Pairs using a Hash Map. Understand the approach, C++ solution, and O(n) time complexity.
#Nvidia#Meta#google#amazon
CH
Chakradhar
Author at SyntaxFlow
On this page
Problem statement
Approach 1 ā Brute force (check every pair)
Approach 2 ā Better (sort + two pointers)
Approach 3 ā Optimal (hash map, one pass)
Complexity comparison
Interview notes
FAQ
Problem Statement
GivenĀ numsĀ and an integerĀ k, repeatedly remove two numbers that sum toĀ k. Return the maximum number of such removals possible.
Examples:
nums = [1,2,3,4], k = 5 ā 2 nums = [3,1,3,4,3], k = 6 ā 1
The second example is the more interesting one ā three separate 3s could each theoretically pair with another 3 to sum to 6, but only one such pair can actually be formed, since pairing uses up two of the three 3s and leaves the last one stranded. We'll trace all three approaches on nums = [3,1,3,4,3],Ā k = 6 to see how each one handles this correctly.
Approach 1 Ā· Brute Force
Check Every Pair, Skipping Used Numbers
Intuition
The most direct approach: for every number not yet used, scan forward for the first other unused number that completes the sum to k. If one is found, mark both as used and count a pair. This works because any number valued v can pair with any unused number valued k - v ā there's no reason one specific pairing is better than another, so greedily grabbing the first available match never costs you a pair you could have made otherwise.
Algorithm
Create a used array, all initialized to false.
For each index i not yet used, scan forward through j > i for the first unused index where nums[i] + nums[j] == k.
If found, mark both i and j as used and increment the count.
Move to the next unused i and repeat.
Return the total count.
C++ Code
intmaxOperations(vector<int>& nums, int k){
int n = nums.size();
vector<bool> used(n, false);
int count = 0;
for (int i = 0; i < n; i++) {
if (used[i]) continue;
for (int j = i + 1; j < n; j++) {
if (!used[j] && nums[i] + nums[j] == k) {
used[i] = used[j] = true;
count++;
break;
}
}
}
return count;
}
Dry Run
Brute Force O(nĀ²)
Testing every pair to find target sum k = 5.
F
3
0
F
1
1
F
4
2
F
3
3
F
2
4
count = 0
vector<bool> used(5, false);
Iteration: i = 0
Looking for 5 - 3 = 2. Scans forward with j and finds it at index 4.
T
3
0
i
F
1
1
F
4
2
F
3
3
T
2
4
j
Sum: 3 + 2 = 5
count = 1
Mark used[0] and used[4] as true.
Iteration: i = 1
Looking for 5 - 1 = 4. Scans forward and finds it at index 2.
T
3
0
T
1
1
i
T
4
2
j
F
3
3
T
2
4
Sum: 1 + 4 = 5
count = 2
Mark used[1] and used[2] as true.
Iteration: i = 2
Check if used[2] is true.
T
3
0
T
1
1
T
4
2
i
F
3
3
T
2
4
if (used[2]) continue;
Element is already part of a pair. Skipped!
Iteration: i = 3
Looking for 5 - 3 = 2 among unused elements to the right.
T
3
0
T
1
1
T
4
2
F
3
3
i
T
2
4
j
j = 4 is 2, but used[4] is true!
No valid pairs found. count remains 2.
Final Result: Return 2 ā
After `i` reaches the end, we return the total valid pairs found.
T
3
T
1
T
4
F
3
T
2
Return: 2
šØ Complexity Warning: We used an extra array for states O(n) Space, and the nested loops require O(nĀ²) Time. This is highly inefficient for large arrays!
1 / 6
Complexity Analysis
Metric
Value
Why
Time
O(nĀ²)
Each unused index scans forward through the remaining unused ones
Space
O(n)
The used array tracks which indices are already paired
Practical issue
Repeated scanning
Every search restarts from scratch instead of remembering what's already been seen
Approach 2 Ā· Better
Sort, Then Two Pointers
Intuition
Once the array is sorted, the smallest and largest remaining numbers are always the best candidates to test against each other: if they sum to less than k, the smallest number is too small to ever work with anything else remaining, so move past it; if they sum to more than k, the same logic applies to the largest number. This is the same shrinking-window idea used in classic two-sum-on-sorted-array problems.
Algorithm
Sort nums.
Set left = 0 and right = n - 1.
While left < right: if nums[left] + nums[right] == k, count a pair and move both pointers inward.
If the sum is less than k, move left forward; if greater, move right backward.
Return the total count once the pointers meet.
C++ Code
intmaxOperations(vector<int>& nums, int k){
sort(nums.begin(), nums.end());
int left = 0, right = nums.size() - 1;
int count = 0;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == k) {
count++;
left++;
right--;
} elseif (sum < k) {
left++;
} else {
right--;
}
}
return count;
}
Dry Run
Sort & Initialize
Target sum k = 6. First, we sort the array to enable two pointers.
1
0
left
2
1
3
2
4
3
6
4
right
k = 6
count = 0
sort(nums.begin(), nums.end()); executed.
Iteration 1: Sum > Target
Check the sum of elements at `left` and `right`.
1
0
left
2
1
3
2
4
3
6
4
right
sum = 1 + 6 = 7
7 > 6 (Sum is too large)
Because the array is sorted, we need a smaller number. Action: right--
Iteration 2: Sum < Target
Right pointer shifted. Check sum again.
1
0
left
2
1
3
2
4
3
right
6
4
sum = 1 + 4 = 5
5 < 6 (Sum is too small)
Because the array is sorted, we need a larger number. Action: left++
Iteration 3: Match Found!
Left pointer shifted. Check sum again.
1
0
2
1
left
3
2
4
3
right
6
4
sum = 2 + 4 = 6 (MATCH)
Found target! Both elements are consumed. Action: count++, left++, right--
Loop Terminates
Both pointers have moved inward.
1
0
2
1
3
2
L / R
4
3
6
4
while (left < right) is now false.
An element cannot be paired with itself.
Final Result: Return 1 ā
Algorithm completes in a single pass.
1
2
3
4
6
Return: 1
Optimization Win: Because we sorted the array O(N log N), we could search for pairs from both ends in just O(N) time without using any extra memory tracking arrays. Overall Space Complexity: O(1).
1 / 6
Complexity Analysis
Metric
Value
Why
Time
O(n log n)
Dominated by the initial sort; the two-pointer scan itself is O(n)
Space
O(1) extra
No auxiliary array beyond the sort's own internal overhead
Improvement
No repeated scanning
Each pointer only ever moves forward, unlike the brute-force restart-from-scratch search
Approach 3 Ā· Optimal
Hash Map: One Pass, Track What's Still Available
Intuition
Sorting costs O(n log n) just to enable the two-pointer trick ā but the real question at each number is simple: "have I already seen its complement, and is one still unused?" A hash map answers that in O(1) per lookup, with no sorting required at all. Scan once: if the complement is available, use it up and count a pair; otherwise, remember the current number for later.
Algorithm
Create an empty frequency map freq.
For each num in nums, compute complement = k - num.
If freq[complement] > 0, a partner is available: decrement freq[complement] and count a pair.
Otherwise, increment freq[num] so a later number can find it.
Return the total count after the scan.
C++ Code
intmaxOperations(vector<int>& nums, int k){
unordered_map<int, int> freq;
int count = 0;
for (int num : nums) {
int complement = k - num;
if (freq[complement] > 0) {
freq[complement]--;
count++;
} else {
freq[num]++;
}
}
return count;
}
Dry Run
Hash Map (One Pass)
Target sum k = 5. Array: [3, 1, 4, 3, 2]
3
1
4
3
2
freq (unordered_map)
Empty
k = 5
count = 0
Iteration 1: Add to Map
Process the first element.
3
num
1
4
3
2
freq (unordered_map)
3
1
comp = 5 - 3 = 2
freq[2] is 0. Action: freq[3]++
Iteration 2: Add to Map
Process the second element.
3
1
num
4
3
2
freq (unordered_map)
3
1
1
1
comp = 5 - 1 = 4
freq[4] is 0. Action: freq[1]++
Iteration 3: Pair Found!
Process the third element.
3
1
4
num
3
2
freq (unordered_map)
3
1
1
0
comp = 5 - 4 = 1 freq[1] > 0 is TRUE!
Pair (1, 4) created. Action: freq[1]--, count++
Iteration 5: Another Pair!
Fast-forward to index 4 (Assuming index 3 added another 3 to map).
3
1
4
3
2
num
freq (unordered_map)
3
1
1
0
comp = 5 - 2 = 3 freq[3] > 0 is TRUE!
Pair (3, 2) created. Action: freq[3]--, count++
Final Result: Return 2 ā
Algorithm completes in a single pass.
3
1
4
3
2
Return: 2
Hash Map Trade-off: We achieved O(N) Time without needing to sort the array first! However, this comes at the cost of O(N) Space to maintain the hash map.
1 / 6
Complexity Analysis
Metric
Value
Why
Time
O(n) average
A single pass, with O(1) average hash map lookups and updates
Space
O(n)
The frequency map can hold up to n distinct values
Why optimal
Best time complexity
Avoids sorting entirely, trading some memory for a faster single pass
Interview Notes
How to talk through it
Frame the whole problem as complement counting right away ā "for each number, does its complement already exist and is it still free?" ā since that framing leads naturally to both the two-pointer and hash map solutions.
Mention the O(n log n) sort-and-two-pointer version as a solid, low-memory answer, then present the hash map version as the faster alternative, explicitly naming the time-versus-space trade-off between them.
Call out the self-complement case (k - num == num) proactively ā walking through why [3,1,3,4,3] only yields 1 pair, not more, is exactly the kind of detail that distinguishes a careful answer from a rushed one.
Common follow-ups
"What if you need the actual pairs, not just the count?" ā store lists of available indices per value instead of counts, and pop an index whenever a match is used.
"Can this be done without extra space?" ā the two-pointer approach after sorting is the answer, with the trade-off of paying for the sort.
"What if nums can contain negative numbers?" ā both approaches handle negatives naturally ā sorting and hashing don't care about sign, only value.
Edge cases to mention
Empty array or single element ā 0 operations, since no pair can be formed.
All elements identical and equal to k / 2 ā the answer is floor(n / 2), exercising the self-complement case fully.
No pairs at all sum to k ā both approaches correctly return 0 without special-casing.
Related problems
Two Sum
Two Sum II ā Input Array Is Sorted
3Sum / 4Sum
Subarray Sum Equals K (complement counting with running sums)
Frequently Asked Questions
What is the key insight for Max Number of K-Sum Pairs?
Every number's usefulness comes down to whether its complement, k minus the number, has already appeared and is still unused ā reducing the whole problem to a lookup rather than a search.
Which approach should I lead with in an interview?
Explain the complement-counting framing first, then present the hash map solution as your primary answer for its O(n) time, while being ready to discuss the sort-and-two-pointer alternative if memory is a concern.
Why is the case where a number equals its own complement tricky?
A value like 3 with k = 6 is its own complement, so a group of duplicate 3s can only be paired two at a time ā the implementation must decrement availability on each successful match to avoid over- or under-counting.
What is the time and space complexity of the optimal solution?
The hash map approach runs in O(n) average time with a single pass over the array, using O(n) extra space to track how many of each value are still available to pair.
