1679. Max Number of K Sum Pairs

Problem Statement Source

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 <= 10&5
• 1 <= nums[i] <= 10^9
• 1 <= k <= 10^9

Solution:

1. First approach is simple brute force method:
   • Flag the visited pair to any number (for eg. -1)
   • Time Complexity :- BigO(N^2)
   • Space Complexity :- BigO(1)

class Solution {
	public int maxOperations(int[] nums, int k) {
		int count = 0;
		for(int i = 0; i < nums.length; i++){
			if(nums[i] == -1) continue;
			for(int j = i + 1; j < nums.length; j++){
				if(nums[j] == -1) continue;
				if(nums[i] + nums[j] == k){
					count++;
					nums[i] = -1;
					nums[j] = -1;
					break;
				}
			}
		}
		return count;
	}
}

2. In Second approach we’ll be sorting the array.
   • First sort the array in O(NLogN).
   • Now, take two pointers where i = 0 and j = array.length - 1 ;
   • sum == target; i ++ and j—;
   • sum > target; j—;
   • sum ⇐ target; i++
   • TC = O(NLogN) + O(N) → O(NLogN)
   • SC = O(1)

class Solution {
    public int maxOperations(int[] nums, int k) {
        Arrays.sort(nums);
        int count = 0;
        int i = 0;
        int j = nums.length - 1;
        while(i < j){
            int sum = nums[i] + nums[j];
            if(sum == k) {
                count++;
                i++;
                j--;
            }
            else if(sum > k) j--;
            else i++;
        }
        return count;
    }
}

3. In third approach, we’ll use hashmap.

class Solution {
	public int maxOperations(int[] nums, int k) {
		Map<Integer, Integer> freqMap = new HashMap<>();
	
		int count = 0;
		for (int i = 0; i < nums.length; i++) {
			int target = k - nums[i];
			
			if (freqMap.containsKey(target) && freqMap.get(target) > 0) {
				freqMap.put(target, freqMap.get(target) - 1);
				count++;
			} else{
				freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0)+1);
			}
		}
		return count;
	}
 
}