Solving tips
- It's Two Sum but counting DISJOINT pairs; sort then two pointers from both ends, or one-pass hash-map of unmatched counts.
- Two-pointer: sum==k count and move both inward, sum<k move left up (smallest can't pair with anything), sum>k move right down.
- Hash-map version: for each x check waiting[k-x] BEFORE incrementing waiting[x], which prevents an element pairing with itself when k is even.
- Sort+two-pointers is O(n log n) time / O(1) space; hash map is O(n) time / O(n) space. On a match move both pointers, never one.
Problem
You are given an integer array nums and an integer k. In one operation you may pick two elements of the array whose values add up to exactly k, and remove both of them from the array.
Return the maximum number of such operations you can perform. Each element can be used in at most one operation — once removed, it is gone.
Examples
Example 1
Input: nums = [1, 2, 3, 4], k = 5
Output: 2
Pair (1, 4) and pair (2, 3) both sum to 5, so two operations are possible.
Example 2
Input: nums = [3, 1, 3, 4, 3], k = 6
Output: 1
Only one pair of 3s can be removed (3 + 3 = 6); the remaining [1, 4, 3] has no pair summing to 6.
Example 3
Input: nums = [2, 2, 2, 2], k = 4
Output: 2
The four 2s form two disjoint pairs, each summing to 4.
Constraints
1 <= nums.length <= 10^5 — an O(n^2) pairing scan is too slow.1 <= nums[i] <= 10^91 <= k <= 10^9
Think about it first
Hint 1
This is Two Sum, except you must count how many disjoint pairs exist, not just find one. What made Two Sum fast?
Hint 2
If the array were sorted, where would the most promising partner for the smallest element be? What can you conclude when the smallest + largest is less than `k`? Greater than `k`?
Hint 3
Sort, then put one pointer at each end. If the two values sum to `k`, count a pair and move both pointers inward; if the sum is too small the left value can never pair with anything (everything remaining is ≤ the current right), so advance `left`; if too big, retreat `right`. Alternatively, one pass with a hash map of "unmatched counts" does it without sorting.
TL;DR
Sort + two pointers from both ends, O(n log n) time / O(1) extra space — or a one-pass hash-map count, O(n) time / O(n) space.
Approach 1 — Brute force
For every element, scan the rest of the array for an unused partner that completes the sum, marking both as used when found.
from typing import List
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
used = [False] * len(nums)
ops = 0
for i in range(len(nums)):
if used[i]:
continue
for j in range(i + 1, len(nums)):
if not used[j] and nums[i] + nums[j] == k:
used[i] = used[j] = True
ops += 1
break
return ops
Complexity: O(n^2) time, O(n) space.
With n up to 10^5, n^2 = 10^10 comparisons — far past the time limit.
Approach 2 — Sort + two pointers
The insight: after sorting, the smallest and largest remaining values bracket every possible pair sum. If nums[left] + nums[right] < k, then nums[left] is too small to pair with anything still available (the right pointer is already at the largest remaining value), so left can be discarded. Symmetrically, if the sum is too large, nums[right] can never be used. If the sum equals k, greedily take the pair — matching extremes never blocks a better pairing.
from typing import List
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
nums.sort()
left, right = 0, len(nums) - 1
ops = 0
while left < right:
total = nums[left] + nums[right]
if total == k:
ops += 1
left += 1
right -= 1
elif total < k:
left += 1
else:
right -= 1
return ops
Walkthrough on nums = [3, 1, 3, 4, 3], k = 6 → sorted [1, 3, 3, 3, 4]:
| left | right | sum | action |
|---|
| 0 (1) | 4 (4) | 5 | too small → left += 1 |
| 1 (3) | 4 (4) | 7 | too big → right -= 1 |
| 1 (3) | 3 (3) | 6 | pair! ops = 1, move both |
| 2 | 2 | — | pointers met, stop |
Answer: 1. ✓
Complexity: O(n log n) time (sorting dominates), O(1) extra space beyond the sort.
Approach 3 — One-pass hash map
The insight: you don’t need order at all — you need to know, for each incoming value x, whether an unmatched k - x has already been seen. Keep a counter of unmatched values: if a complement is waiting, consume it and count an operation; otherwise record x as waiting. This is the classic Two Sum hash-map idea extended to multiplicities.
from collections import Counter
from typing import List
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
waiting: Counter[int] = Counter()
ops = 0
for x in nums:
need = k - x
if waiting[need] > 0:
waiting[need] -= 1
ops += 1
else:
waiting[x] += 1
return ops
Walkthrough on nums = [1, 2, 3, 4], k = 5:
x = 1: need 4, none waiting → waiting = {1: 1}x = 2: need 3, none waiting → waiting = {1: 1, 2: 1}x = 3: need 2, one waiting → consume it, ops = 1x = 4: need 1, one waiting → consume it, ops = 2
Answer: 2. ✓
Complexity: O(n) time, O(n) space.
Common pitfalls
- Self-pairing when
k is even: with the hash map, checking waiting[need] before incrementing waiting[x] is what stops a single element from pairing with itself when x == k - x.
- Double counting: counting every index pair
(i, j) with nums[i] + nums[j] == k instead of disjoint pairs — each element may be removed only once.
- Two-pointer equal case: on a match you must move both pointers; moving only one either recounts an element or loops forever.
- Values reach 10^9, so
k - x can be negative-free but large — no issue in Python, but in fixed-width languages watch for overflow.
Pattern takeaway
Sorted two-pointers works whenever an extreme element can be proved dead: if the smallest plus the largest is still short of the target, the smallest can never participate and is safely discarded (and symmetrically for the largest). That discard argument — not the sortedness itself — is what makes the linear sweep correct, and it is the same argument you’ll reuse in Two Sum II and container-style problems.