LeetCode Challenge #1679. Max Number of K-Sum Pairs

Question 13 of 75 - LeetCode Weekly Challenge

LeetCode Challenge #1679. Max Number of K-Sum Pairs

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⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹

Video Solution

C++ Solution

				
					class Solution {
public:
     int maxOperations(vector<int>& nums, int k) {

        sort(nums.begin(),nums.end());

        if(nums.size()<2)
            return 0;

        int left=0;
        int right=nums.size()-1;
        int count=0;

        while(left<right)
        {
            if((nums[left]+nums[right])<k)
                left++;

            else if((nums[left]+nums[right])>k)
                right--;

            else
            {
                count++;
                left++;
                right--;
            }
        }
        return count;
    }
};

Code Explanation

In this program we have to find the maximum number of pairs of elements in the vector ‘nums’ whose sum is equal to given target ‘k’ .

We will do this by using “two-pointer approach”.

Let’s see the step-by-step approach of the code:

First of all the array should be in a sorted form so, we sort the ‘nums’ in ascending order using ‘sort(nums.begin( ) , nums.end( ) ) ‘ this is a very important step for the two- pointer approach to work efficiently.

Next we check the size of the vector , if the size of the vector is less than 2 , it means no pairs or groups can be formed and the function returns 0.

Now we initializes two pointers , ‘left’ and ‘right’ , where left points to the beginning of the sorted array and right points towards the end .

After that, we initializes a variable ‘count’ to 0 , for tracking the number of pairs found.

‘While’ loop has been used here in which the loop will continue till the point when ‘left’ is less than ‘right’

In this loop :

if the sum of of elements of positions of ‘left’ and ‘right’ is less than the target ‘k’ .

if the sum is less, it means we need a larger sum , so we simply increment ‘left’ .

if the the sum is greater, that means we need a smaller sum so we decrements ‘right’ .

if the the sum is equal to ‘k’ , it means the pair is found, and we increment the count ( count ++) and move both pointers (‘left++’ and ’right- -‘ ) so that we don’t count these elements again.

The loop will continue until ‘left’ is no longer less than ‘right’.

Finally, the function returns the total count pairs found .

Question 13 of 75 - LeetCode Weekly Challenge