You are given an integer array
numsand an integer
x. In one operation, you can either remove the leftmost or the rightmost element from the array
numsand subtract its value from
x. Note that this modifies the array for future operations.
Return the minimum number of operations to reduce
xto exactly 0 if it's possible, otherwise, return -1.
Input: nums = [1,1,4,2,3], x = 5 Output: 2 Explanation: The optimal solution is to remove the last two elements to reduce x to zero.
Input: nums = [5,6,7,8,9], x = 4 Output: -1
Input: nums = [3,2,20,1,1,3], x = 10 Output: 5 Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.
1 <= nums.length <= 105
1 <= nums[i] <= 104
1 <= x <= 109
import pytest from .Day14_MinimumOperationsToReduceXToZero import Solution s = Solution() @pytest.mark.parametrize( "nums,x,expected", [([1, 1, 4, 2, 3], 5, 2), ([5, 6, 7, 8, 9], 4, -1), ([3, 2, 20, 1, 1, 3], 10, 5)], ) def test_min_operations(nums, x, expected): assert s.minOperations(nums, x) == expected
from typing import List class Solution: def minOperations(self, nums: List[int], x: int) -> int: total = sum(nums) remainder = total - x n = len(nums) largest_subarray_len = -1 current_sum = 0 j = 0 for i in range(n): current_sum += nums[i] while current_sum > remainder and j <= i: current_sum -= nums[j] j += 1 if current_sum == remainder: largest_subarray_len = max(largest_subarray_len, i - j + 1) if largest_subarray_len == -1: return largest_subarray_len return n - largest_subarray_len
There were 2 hints in the problem that I ended up using.
Think in reverse; instead of finding the minimum prefix + suffix, find the maximum subarray.
Finding the maximum subarray is standard and can be done greedily.
The Max Sub Array Problem is reasonably straightforward to solve. The bit I found tricky initially was figuring out exactly what max subarray to look for. I tried to avoid doing any pre-processing of the array but could not come up with anything good there. Finding a sub array without always going over the whole array appears to be too hard. Turns out a good solution is to think in reverse (as the hint said) and find the largest sub array what is
sum(nums) - x. If you know the length of that sub array you can subtract its length from the length of
nums to get the number of operations.
Even though we do sum the array at first the solution is still
O(n) so not too bad.