Max Number of K-Sum Pairs
Count the most operations that each remove two numbers summing to k, by sorting the array and moving two pointers toward each other.
Problem Understanding
Max Number of K-Sum Pairs (LeetCode 1679): given an integer array nums and an integer k, one operation picks two numbers that sum to k and removes them. Return the maximum number of operations you can perform.
Examples: [1, 2, 3, 4], k = 5 → 2; [3, 1, 3, 4, 3], k = 6 → 1.
The Intuition: Two Sum, Repeated
This is Two Sum II run until the pointers meet, counting every match instead of stopping at the first.
- Sort so sums move predictably.
- Too small: the left value has no partner left; move l.
- Too big: the right value has no partner left; move r.
- Exactly k: count it and remove both.
Interactive Walkthrough
k = 6
SORT
sorted nums
l
0
1
2
3
r
4
l + r
5
Operations
0
Sort: [1, 3, 3, 3, 4]. l at the smallest, r at the largest
Next
1 + 4 = 5 < 6: only a bigger left value can help. l moves right
nums
k
The array is shown sorted. l and r are filled; pairs that sum to k turn green, and values skipped for having no partner turn grey. Try Duplicates to see equal values pair with each other.
Dry Run Table
Input: nums = [3, 1, 3, 4, 3], k = 6. Sorted: [1, 3, 3, 3, 4].
| l | r | Sum | Action | count |
|---|---|---|---|---|
| 0 (1) | 4 (4) | 5 | too small, l + 1 | 0 |
| 1 (3) | 4 (4) | 7 | too big, r − 1 | 0 |
| 1 (3) | 3 (3) | 6 | pair | 1 |
| 2 | 2 | pointers met | 1 |
Answer: 1.
The Solution Template
Sort, then the three-way comparison of Two Sum II inside a loop that keeps counting.
Max Number of K-Sum Pairs Code
1var maxOperations = function(nums, k) {2 nums.sort((a, b) => a - b);3 let l = 0, r = nums.length - 1, count = 0;4 while (l < r) {5 const total = nums[l] + nums[r];6 if (total === k) {7 count++;8 l++;9 r--;10 } else if (total < k) {11 l++;12 } else {13 r--;14 }15 }16 return count;17};
Edge Cases & Common Mistakes
- Equal values:
[2, 2, 2, 2]with k = 4 gives 2; two different indices may hold the same value. - Using one number twice: l < r guarantees two different elements.
- No pairs: the pointers meet without a match; return 0.
- JavaScript sort: pass a numeric comparator, or [10, 9] sorts as text.
Summary
Sort, then move two pointers inward: count and remove on a match, move l when the sum is small and r when it is big. O(n log n) time, O(1) extra space.
More practice: DSA interview questions with answers · patterns cheat sheet