Day 14 - Minimum Operations to Reduce X to Zero

The Problem

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it's possible, otherwise, return -1.

Example 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.

Example 2:

Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:

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.

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104
• 1 <= x <= 109

My Tests

Link to code

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

My Solution

Link to code

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

Analysis

My Commentary

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.