#1679
Max Number of K-Sum Pairs
Medium HashMap pairing
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In one operation you remove two numbers that sum to k. Return the most operations you can do.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: how many disjoint pairs sum to k?
Why this works: keep numbers waiting for a partner; when x arrives and k - x is waiting, use it up.
Example: [3, 1, 3, 4, 3], k = 6
3 waits, 1 waits3 pairs with 3 → 1 op4 waits, 3 waits → answer 1
✦Hints open one at a time
This is Two Sum, but each number can be used once.
Keep counts of unmatched numbers; when the complement is available, use it up.
↗Approach
For each x, if count[k − x] > 0, decrement it and add one operation; otherwise increment count[x].
</>Solution (Java)
import java.util.*;
class Solution {
public int maxOperations(int[] nums, int k) {
Map<Integer, Integer> waiting = new HashMap<>();
int ops = 0;
for (int x : nums) {
int need = k - x;
int c = waiting.getOrDefault(need, 0);
if (c > 0) {
waiting.put(need, c - 1); // pair x with a waiting partner
ops++;
} else {
waiting.merge(x, 1, Integer::sum);
}
}
return ops;
}
}!Common mistake
Counting x with itself when x = k − x and only one copy is available — checking before storing x avoids it.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Hashing
🎬 Episodes 37–39: video coming soon