You are given an integer array
nums
and an integerk
.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
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)