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.
This approach involves using a hashmap to store the frequency of each number in the array. For each number in the array, check if the complement (k - current number) exists in the hashmap. If it does, form a pair and decrease the frequency of both the current number and its complement in the hashmap. This ensures that no number is reused in forming pairs, optimizing the number of operations possible.
The C solution utilizes a fixed-size array to simulate a hashmap because the constraints allow it. It iterates over all elements while checking if the complement needed to make up k exists in the hashmap. If it does, a pair is formed, and the operations count is increased.
Time Complexity: O(n) because it involves a single pass through the array and constant-time operations for the hash table.
Space Complexity: O(n) to store the counts in the hash map.
First sort the array, which allows the use of a two-pointer technique to find pairs. One pointer starts at the beginning and the other at the end of the sorted array. If the sum of the elements at these pointers equals k, increase the operations count and move both pointers. If the sum is less than k, move the left pointer to increase the sum, otherwise, move the right pointer to decrease the sum, thus efficiently finding all possible pairs.
This C solution first sorts the array and then applies a two-pointer technique to count the number of k-sum pairs efficiently, adjusting pointers based on their summed value relative to k.
Time Complexity: O(n log n) due to sorting, with a subsequent O(n) linear traversal using two pointers.
Space Complexity: O(1) for the additional pointers only.
We sort nums. Then l and r point to the first and last elements of nums respectively, and we compare the sum s of the two integers with k.
s = k, it means that we have found two integers whose sum is k. We increment the answer and then move l and r towards the middle;s > k, then we move the r pointer to the left;s < k, then we move the l pointer to the right;l geq r.After the loop ends, we return the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of nums.
We use a hash table cnt to record the current remaining integers and their occurrence counts.
We iterate over nums. For the current integer x, we check if k - x is in cnt. If it exists, it means that we have found two integers whose sum is k. We increment the answer and then decrement the occurrence count of k - x; otherwise, we increment the occurrence count of x.
After the iteration ends, we return the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of nums.
| Approach | Complexity |
|---|---|
| Using HashMap for Frequency Counting | Time Complexity: O(n) because it involves a single pass through the array and constant-time operations for the hash table. |
| Two Pointer Technique on Sorted Array | Time Complexity: O(n log n) due to sorting, with a subsequent O(n) linear traversal using two pointers. |
| Sorting | — |
| Hash Table | — |
| 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 |
Max Number of K-Sum Pairs | Live Coding with Explanation | Leetcode - 1679 • Algorithms Made Easy • 12,273 views views
Watch 9 more video solutions →Practice Max Number of K-Sum Pairs with our built-in code editor and test cases.
Practice on FleetCode