Max Number of K-Sum Pairs
MedPrompt
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.
Example 1:
Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.Example 2:
Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a brute-force method to find all possible pairs. It involves iterating through the array with two nested loops to check every unique pair of numbers. To prevent using the same number in multiple pairs, a boolean array is used to mark numbers that have been included in a pair.
Algorithm
- Initialize
operationsto 0. - Create a boolean array
usedof the same size asnums, and initialize all its values tofalse. - Iterate through the
numsarray with an indexifrom0ton-1. - If
used[i]istrue, it means the number has already been paired, so wecontinueto the next element. - Inside the first loop, start a second, nested loop with an index
jfromi + 1ton-1. - If
used[j]istrue,continueto the next element. - Check if
nums[i] + nums[j] == k. - If the sum is equal to
k, we have found a pair. Incrementoperations, setused[i]andused[j]totrue, andbreakfrom the inner loop sincenums[i]has now been used. - After the loops complete, return the total
operationscount.
Walkthrough
The core idea is to examine every possible pair of elements (nums[i], nums[j]) in the array. We use a primary loop to pick the first element nums[i] and a nested loop to pick the second element nums[j], ensuring j > i to avoid duplicate pairs and self-pairing.
To handle the constraint that each number can only be used once, we maintain a boolean array used of the same size as nums. When we find a pair (nums[i], nums[j]) that sums to k, and neither element has been used before (i.e., used[i] and used[j] are both false), we increment our operation count and set both used[i] and used[j] to true. We then break the inner loop for the current i because nums[i] is now part of a pair and cannot be used again.
import java.util.Arrays; class Solution { public int maxOperations(int[] nums, int k) { int operations = 0; int n = nums.length; boolean[] used = new boolean[n]; for (int i = 0; i < n; i++) { if (used[i]) { continue; } for (int j = i + 1; j < n; j++) { if (used[j]) { continue; } if (nums[i] + nums[j] == k) { operations++; used[i] = true; used[j] = true; break; // Move to the next i since nums[i] is now used } } } return operations; }}Complexity
Time
O(n^2), where n is the number of elements in the array. The nested loops result in a quadratic number of comparisons in the worst case.
Space
O(n), where n is the number of elements in the array. This space is used for the `used` boolean array to track which elements have been paired.
Trade-offs
Pros
Simple to understand and implement.
Works correctly for small input sizes.
Cons
Extremely inefficient for large arrays, likely resulting in a 'Time Limit Exceeded' error on competitive programming platforms.
A significantly better approach is to first sort the array. Once sorted, we can use the two-pointer technique. We place one pointer at the beginning of the array and another at the end. By comparing the sum of the values at these pointers with k, we can efficiently find pairs by moving the pointers inward.
Algorithm
- Sort the input array
numsin non-decreasing order. - Initialize an integer
operationsto 0. - Initialize two pointers:
leftat the start of the array (index 0) andrightat the end of the array (indexn-1). - Loop while
leftis less thanright. - Calculate the sum of the elements at the two pointers:
sum = nums[left] + nums[right]. - If
sum == k, a pair is found. Incrementoperations, move the left pointer one step to the right (left++), and move the right pointer one step to the left (right--). - If
sum < k, the sum is too small. To increase it, move theleftpointer one step to the right (left++). - If
sum > k, the sum is too large. To decrease it, move therightpointer one step to the left (right--). - The loop terminates when
leftandrightpointers meet or cross. Return the finaloperationscount.
Walkthrough
This method leverages the fact that if the array is sorted, we can make intelligent decisions about which elements to pair. After sorting nums, we set up a left pointer at index 0 and a right pointer at the last index.
We then check the sum nums[left] + nums[right].
- If the sum equals
k, we've found a valid pair. We count this operation and move both pointers inward (left++,right--) to search for other potential pairs. - If the sum is less than
k, we need a larger value to reach the targetk. Since the array is sorted, we move theleftpointer to the right to include a larger number in the sum. - If the sum is greater than
k, we need a smaller value. We move therightpointer to the left to include a smaller number.
This process continues until the pointers cross (left >= right), at which point we have found all possible pairs.
import java.util.Arrays; class Solution { public int maxOperations(int[] nums, int k) { Arrays.sort(nums); int left = 0; int right = nums.length - 1; int operations = 0; while (left < right) { int currentSum = nums[left] + nums[right]; if (currentSum == k) { operations++; left++; right--; } else if (currentSum < k) { left++; } else { // currentSum > k right--; } } return operations; }}Complexity
Time
O(n log n), dominated by the initial sorting of the array. The subsequent two-pointer scan takes only O(n) time.
Space
O(log n) or O(n), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types has an average space complexity of O(log n).
Trade-offs
Pros
Much more efficient than the brute-force approach.
Space-efficient, as it can be done with O(log n) or O(1) extra space depending on the sort implementation and if in-place sorting is allowed.
Cons
The time complexity is dominated by the sorting step, making it less efficient than the hash map approach.
Modifies the input array by sorting it, which might not be permissible in all contexts. A copy would require O(n) space.
The most time-efficient solution uses a hash map to act as a frequency counter. By iterating through the array once, we can check for the existence of a complementary number (k - num) in constant time on average. This avoids the need for sorting or nested loops.
Algorithm
- Initialize
operationsto 0 and create an empty hash map,frequencyMap, to store number frequencies. - Iterate through each
numin thenumsarray. - For each
num, calculate its required complement:complement = k - num. - Check if the
complementexists as a key infrequencyMapand has a value (frequency) greater than 0. - If it does, a pair is found. Increment
operationsand decrement the frequency of thecomplementin the map. - If the
complementis not found or its frequency is 0, it means we haven't found a match for the currentnumyet. Store the currentnumin the map by incrementing its frequency count. - After iterating through all numbers, return the total
operationscount.
Walkthrough
This approach provides a linear time solution by using a hash map to keep track of the frequencies of numbers we have encountered. We iterate through the nums array just once.
For each number num, we calculate the complement we need to form a sum of k (i.e., complement = k - num). We then look in our frequencyMap for this complement.
- If the
complementis in the map and its count is positive, it means we have a previously seen number that can form a pair with the currentnum. We increment ouroperationscount and decrement the count of thecomplementin the map to signify it has been used. - If the
complementis not in the map or its count is zero, we cannot form a pair at this moment. Instead, we add the currentnumto the map (or increment its count if it's already there), making it available for future numbers to pair with.
This single-pass strategy ensures that every number is processed efficiently to find its partner.
import java.util.HashMap;import java.util.Map; class Solution { public int maxOperations(int[] nums, int k) { Map<Integer, Integer> frequencyMap = new HashMap<>(); int operations = 0; for (int num : nums) { int complement = k - num; if (frequencyMap.getOrDefault(complement, 0) > 0) { // Found a pair, use the complement operations++; frequencyMap.put(complement, frequencyMap.get(complement) - 1); } else { // No pair found, store the current number for future matches frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1); } } return operations; }}Complexity
Time
O(n), where n is the number of elements in the array. This is because we iterate through the array once, and hash map operations (put and get) take, on average, O(1) time.
Space
O(n) in the worst case. If all elements in `nums` are distinct and no pairs are formed, the hash map will store up to `n` entries.
Trade-offs
Pros
Optimal time complexity of O(n).
Processes the array in a single pass.
Cons
Requires extra space to store the frequency map, which can be up to O(n) in the worst case.
Solutions
Solution
class Solution {public int maxOperations(int[] nums, int k) { Arrays.sort(nums); int l = 0, r = nums.length - 1; int ans = 0; while (l < r) { int s = nums[l] + nums[r]; if (s == k) { ++ans; ++l; --r; } else if (s > k) { --r; } else { ++l; } } return ans; }}class Solution {public: int maxOperations(vector<int> &nums, int k) { sort(nums.begin(), nums.end()); int cnt = 0; int i = 0, j = nums.size() - 1; while (i < j) { if (nums[i] + nums[j] == k) { i++; j--; cnt++; } else if (nums[i] + nums[j] > k) { j--; } else { i++; } } return cnt; }};class Solution: def maxOperations(self, nums: List[int], k: int) -> int: nums . sort() l, r, ans = 0, len(nums) - 1, 0 while l < r: s = nums[l] + nums[r] if s == k: ans += 1 l, r = l + 1, r - 1 elif s > k: r -= 1 else: l += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.