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.
For example:
nums = [1,2,3,4]
and k = 5
, the answer is 2. We remove 1 and 4, then 2 and 3.nums = [3,1,3,4,3]
and k = 6
, the answer is 1. We remove two 3s.Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 10^9
How would you approach solving this problem efficiently?
A brute force solution would involve iterating through all possible pairs in the array and checking if their sum equals k
. If a pair is found, increment the operation count and remove those elements from the array. This process repeats until no such pairs are found.
function maxOperationsBruteForce(nums, k):
count = 0
while True:
found = False
for i from 0 to nums.length - 1:
for j from i + 1 to nums.length - 1:
if nums[i] + nums[j] == k:
remove nums[j] // Remove the larger index first to avoid shifting issues
remove nums[i]
count = count + 1
found = True
break // Restart the outer loop after removing elements
if found:
break
if not found:
return count
A more efficient solution involves using a hash map to store the frequency of each number in the array. Iterate through the array, and for each number num
, check if k - num
exists in the hash map. If it does, decrement the frequency of both num
and k - num
in the hash map (or remove them if the frequency becomes zero) and increment the operation count. If k - num
does not exist, add num
to the hash map (or increment its frequency if it already exists).
function maxOperationsOptimal(nums, k):
count = 0
freqMap = {}
for num in nums:
complement = k - num
if complement in freqMap and freqMap[complement] > 0:
count = count + 1
freqMap[complement] = freqMap[complement] - 1
if freqMap[complement] == 0:
remove complement from freqMap
else:
if num in freqMap:
freqMap[num] = freqMap[num] + 1
else:
freqMap[num] = 1
return count
from collections import Counter
def maxOperations(nums, k):
count = 0
freq = Counter(nums)
for num in nums:
if freq[num] > 0:
complement = k - num
if complement in freq and freq[complement] > 0:
if num == complement and freq[num] < 2:
continue
count += 1
freq[num] -= 1
freq[complement] -= 1
return count
k
, the function should return 0.num == k - num
. We need to ensure that there are at least two of these numbers.