LeetCode — Max Number of K-Sum Pairs
Problem Link: https://leetcode.com/problems/max-number-of-k-sum-pairs/
Problem Description: 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.Approach Used: HashMap(Approach 1), Sorting (Approach 2)
Explanation: In this question, we need to find all the pairs in the array whose sum is equal to k. Also, one element (any number at a particular index) cannot be part of two pairs. And since constraints say that all numbers are positive, so we can discard all the numbers greater than k since they can’t pair with any other number to form k. There are two ways we can do this problem.
In the first approach, since for every number we need to find another number whose sum with the current number is equal to k or simply whose value is equal to ‘k-current_number’. We can do this in O(N) time complexity and O(N) space complexity by storing all the numbers with their frequencies in a map. So whenever we come at a number we reduce its frequency and check if there exists another number in the map which is equal to ‘k-current_number’ and has a frequency greater than 0.
The second approach is using the two-pointer method. This approach works in O(1) space and O(N log N) time. For this approach, we will have to sort the array first. Then we keep one pointer at beginning of the array and another at the end and simultaneously update them based on certain conditions. If the sum of elements at both pointer locations is equal to k then we increment our result and to remove both these number from further calculating we move one step forward (increment left pointer and decrement right pointer). If the sum is greater than k, that means that the right pointer is too large (because if cannot pair with the smallest number it cannot pair with any other. So we decrement right pointer. And lastly, if the sum is smaller than k, then by the same logic we eliminate ‘i’ by incrementing it. This is done until j does not cross ‘i’ because after that the pairs will start repeating.
The second approach gives better performance.
Code: (Java)
public int maxOperationsUsingSet(int[] num, int k){
Map<Integer, Integer> numMap = new HashMap<>();for(int i : num){
if(numMap.containsKey(i))
numMap.put(i, numMap.get(i) + 1);
else
numMap.put(i, 1);
}int ans=0;
for(int i=0; i<num.length; i++){
if(num[i]>k)
continue;int second_num = k-num[i];
int freq = numMap.get(num[i]);
numMap.put(num[i], freq-1);if((numMap.containsKey(second_num)==false || numMap.get(second_num)<=0))
continue;int freq2 = numMap.get(second_num);
numMap.put(second_num, freq2-1);if(freq<=0 || freq2<=0)
continue;ans++;
}return ans;
}public int maxOperationsUsingSorting(int[] num, int k){
Arrays.sort(num);int i,j;
int ans=0;
for(i=0, j=num.length-1; i<num.length && j>=0;){
if(j<=i)
break;if(num[i]+num[j]==k) {
i++;
j--;
ans++;
}
else if(num[i]+num[j]>k)
j--;
else
i++;
}
return ans;
}public int maxOperations(int[] nums, int k) {
// return maxOperationsUsingSet(nums,k);
return maxOperationsUsingSorting(nums,k);
}
Complexity:
Approach 1 (Using maps):
Space Complexity: O(m). where m is the number of unique elements in the array.
Time Complexity: O(N). Two linear loops used for storing in the map and then finding pairs. Here n is the size of the array.
Approach 2 (Using Sorting):
Space Complexity: O(1). No extra space used
Time Complexity: O(N log N). ‘nlogn’ for sorting the array then a linear loop to find the pairs.
Github Code link:
https://github.com/siddhaant-jain/LeetCode/blob/master/DailyChallenge/src/CodeFiles/MaxNumberOfKSumPairs.java
