Minimum Operations to Reduce X to Zero — LeetCode 1658 Python Solution

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.

Example

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.

Python solution

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        s = sum(nums) - x
        vis = {0: -1}
        mx, t = -1, 0
        for i, v in enumerate(nums):
            t += v
            if t not in vis:
                vis[t] = i
            if t - s in vis:
                mx = max(mx, i - vis[t - s])
        return -1 if mx == -1 else len(nums) - mx

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1658. Minimum Operations to Reduce X to Zero is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems