Maximum Number of $k$-sum Pairs

Problem: 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.

Solution

This problem is amenable to the standard two-pointers solution, provided we fist sort the list, nums. The following Python code is self-explantory.

   def maxOperations(nums, k):
        nums = [x for x in nums if x < k] # Remove numbers > k
        nums.sort()
        left = 0
        right = len(nums)-1
        count = 0
        while left < right:
            if nums[left] + nums[right] == k:
                count += 1
                left += 1
                right -= 1
            elif nums[left] + nums[right] > k:
                right -= 1
            else:
                left += 1     
        return count

Runtime: Ignoring the cost of eliminating numbers that are $> k$ and the cost of sorting, we see that the left and right pointers are always moving towards each other. The total number of iterations within the while loop is therefore $n$, and the time complexity is $O(n)$. Since we are only using one local variable count, the space complexity is $O(1)$.

Back to Two Pointers Problems

---

anusha-murali.github.io