Two Pointers for a Linear Solution III (actually, NLogN)

I've written before about two-pointers techniques before. Usually this technique works well with sorted array: have the first pointer in the very left, second pointer in the very right, and do the processing until the pointers cross each other. If the array is already sorted, the solution is linear, otherwise you'll end up with an NLogN. This problem exemplifies the technique: Max Number of K-Sum Pairs - LeetCode

1679. Max Number of K-Sum Pairs

Medium

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 <= 105
• 1 <= nums[i] <= 109
• 1 <= k <= 109

Accepted

5,580

Submissions

10,775

Sort the array first (NLogN). Then apply the two-pointers technique - whenever the sum adds up to k, increment the solution and move the two pointers. Otherwise, just more one accordingly. Code is below, cheers, ACC.

public int MaxOperations(int[] nums, int k)
{
    Array.Sort(nums);

    int left = 0;
    int right = nums.Length - 1;

    int max = 0;
    while (left < right)
    {
        int sum = nums[left] + nums[right];
        if (sum == k)
        {
            left++;
            right--;
            max++;
        }
        else if (sum > k)
        {
            right--;
        }
        else
        {
            left++;
        }
    }
    return max;
}