Max Number of K-Sum Pairs
The key idea
Each number x can only ever pair with its complement k - x. Count how many of each value you have, then each removed pair consumes one x and one (k - x). With a frequency map you settle every value in a single pass; for value x you can form min(count[x], count[k-x]) pairs, and self-pairs (when 2x = k) use count[x] // 2.
Problem
You are given an integer array nums and an integer k.
In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.
Return the maximum number of operations you can perform on the array.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= k <= 10^9
Examples
Input: nums=[1,2,3,4], k=5
Output: 2
Input: nums=[3,1,3,4,3], k=6
Output: 1
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY