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 <= 109This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
Max Number of K-Sum Pairs | Live Coding with Explanation | Leetcode - 1679 • Algorithms Made Easy • 11,173 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