Watch 10 video solutions for Max Number of K-Sum Pairs, a medium level problem involving Array, Hash Table, Two Pointers. This walkthrough by Algorithms Made Easy has 12,273 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 109Problem Overview: Given an integer array and a target value k, you need to form the maximum number of pairs such that each pair sums to k. Every element can be used at most once, so once two numbers form a valid pair they are removed from further consideration.
Approach 1: HashMap Frequency Counting (O(n) time, O(n) space)
This approach scans the array once while storing frequencies in a hash map. For each number x, compute its complement k - x. If the complement already exists in the map with a positive count, you found a valid pair and decrease its frequency. Otherwise, store the current number in the map for future matches. The key insight is that hash lookups are O(1), allowing you to check complements instantly while iterating the array only once. This method works for any unsorted input and is usually the expected optimal solution in interviews. It relies on the efficiency of a hash table combined with a single pass through the array.
Approach 2: Two Pointer Technique on Sorted Array (O(n log n) time, O(1) space)
Another approach sorts the array first, then uses two pointers: one starting at the beginning and the other at the end. At each step, compute the sum of the two values. If the sum equals k, a valid pair is found and both pointers move inward. If the sum is smaller than k, move the left pointer forward to increase the sum. If the sum is larger than k, move the right pointer backward to decrease it. Sorting takes O(n log n) time, but the two-pointer scan itself runs in O(n). This technique is common in problems involving pair sums and demonstrates mastery of the two pointers pattern combined with sorting.
Recommended for interviews: The HashMap approach is typically preferred because it achieves O(n) time without sorting and clearly demonstrates efficient use of a hash-based lookup. The two-pointer solution is also valuable because it shows understanding of sorted array techniques. Explaining both approaches signals strong problem-solving range: hash maps for optimal lookup and pointer techniques for space-efficient scanning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Frequency Counting | O(n) | O(n) | Best general solution for unsorted arrays and interview settings |
| Two Pointer on Sorted Array | O(n log n) | O(1) | Useful when array can be sorted or when minimizing extra memory |