Please see github.com/anusha-murali for all of my repositories.
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]:
Example 2:
Input: nums = [3,1,3,4,3], k = 6
; Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
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)$.