Day 14 - Minimum Operations to Reduce X to Zero
Tags: leetcode, python, challenge
Published: 2021-01-14 16:38:06

## 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](https://github.com/ruarfff/leetcode-jan-2021)

```python
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](https://github.com/ruarfff/leetcode-jan-2021)

```python
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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/i8iq7d5esr8r2yacdt3e.png)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/8z16bgk6paljlhfb5129.png)

## 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](https://medium.com/@rsinghal757/kadanes-algorithm-dynamic-programming-how-and-why-does-it-work-3fd8849ed73d) 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. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/40ddmh0akt38vgaii495.png)

Even though we do sum the array at first the solution is still `O(n)` so not too bad.