MediumNo. 1658
Minimum Operations to Reduce X to Zero — LeetCode 1658 Python Solution
- Pattern
- Sliding Window
- Topics
- Array, Hash Table, Binary Search, Prefix Sum, Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
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) - mxComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
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
| No. | Problem | Difficulty |
|---|---|---|
| 0930 | Binary Subarrays With Sum | Medium |
| 1248 | Count Number of Nice Subarrays | Medium |
| 1477 | Find Two Non-overlapping Sub-arrays Each With Target Sum | Medium |
| 2009 | Minimum Number of Operations to Make Array Continuous | Hard |
| 2251 | Number of Flowers in Full Bloom | Hard |
| 2831 | Find the Longest Equal Subarray | Medium |
Frequently asked questions
- How hard is LeetCode 1658. Minimum Operations to Reduce X to Zero?
LeetCode 1658. Minimum Operations to Reduce X to Zero is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1658. Minimum Operations to Reduce X to Zero?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1658. Minimum Operations to Reduce X to Zero?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1658. Minimum Operations to Reduce X to Zero cover?
LeetCode 1658. Minimum Operations to Reduce X to Zero is tagged Array, Hash Table, Binary Search, Prefix Sum and Sliding Window on LeetCode.