Max Number of K-Sum Pairs
Medium · Two Pointers · Array · Hash Table · Two Pointers · Sorting
Problem
You are given an integer array nums and an integer k. In one operation you pick two numbers from the array (at two different positions) whose sum is exactly k, and remove both of them.
Return the maximum number of operations you can perform. A number can be used in at most one operation, since it is removed when used.
Examples
Input: nums = [1, 2, 3, 4], k = 5 Output: 2
Remove 1 and 4, then 2 and 3.
Input: nums = [3, 1, 3, 4, 3], k = 6 Output: 1
Remove two of the 3s; no other pair sums to 6.
Input: nums = [2, 5, 4, 4, 1, 3, 4, 4, 1, 4, 4, 1, 2, 1, 2, 2, 3, 2, 4, 2], k = 3 Output: 4
Only (1, 2) pairs sum to 3, and there are four 1s.
Constraints
- 1 <= len(nums) <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= k <= 10^9
Approaches
- Sort and close in from both ends — time O(n log n), space O(1) besides the sort
Follow-up
Could you return the pairs themselves in sorted order? What changes when a pair only needs a sum divisible by k?
Related problems
Start free on Cariara · Coding problems · System design studio
