You are given an integer array
numsand an integerk.In one operation, you can pick two numbers from the array whose sum equals
kand 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 <= 1051 <= nums[i] <= 1091 <= k <= 109
Tests
import pytest
from .Day18_MaxNumberOfKSumPairs import Solution
s = Solution()
@pytest.mark.parametrize(
"nums,k,expected",
[
([1, 2, 3, 4], 5, 2),
([3, 1, 3, 4, 3], 6, 1),
([3, 5, 1, 5], 2, 0),
([4, 4, 1, 3, 1, 3, 2, 2, 5, 5, 1, 5, 2, 1, 2, 3, 5, 4], 2, 2),
],
)
def test_max_operations(nums, k, expected):
assert s.maxOperations(nums, k) == expected
Solution
from typing import List
import math
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
max_ops = 0
counts = {}
for n in nums:
if n in counts:
counts[n] = counts[n] + 1
else:
counts[n] = 1
for n in counts:
diff = k - n
if diff in counts and counts[diff] > 0:
ops = 0
if n == k // 2:
ops = math.floor(counts[n] // 2)
else:
ops = min(counts[n], counts[diff])
max_ops += ops
counts[diff] = counts[diff] - ops
counts[n] = counts[n] - ops
return max_ops
Analysis
Commentary
A fairly easy and quick one today. I could definitely have improved it but it will do.
Runtime is O(n). We got over the list once to insert to a map. Then we go over the map keys and do our calculations. Space is O(n) because we created a map to store the counts.
Using a map gives us a very quick way to look up k - n for each n. If we find a match, we can decrement the counts for each number in the match by min(counts[n], counts[diff]) and increment the max operations by that number.
The other case we need to think of is where k - n is k / 2. This will break our implementation so we need to add a check for that case and use math.floor(counts[n] // 2). For example, take k = 2 and [1, 1, 1, 1]. If we used min(counts[n], counts[diff]) we'd get 4 but the correct answer would be 2 which we do get from math.floor(counts[n] // 2).
Top comments (0)