NeetCode #240LC-1658MediumSliding Window
← Back to All Problems#240 · #1658 · Minimum Operations to Reduce X to Zero(将 x 减到 0 的最小操作数)
📌 Problem Statement & Constraints
You are given an array
nums and an integer x. In one operation you may remove either the leftmost or the rightmost element and subtract it from x. Return the minimum number of operations to reduce x to exactly 0, or -1 if impossible. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^4, 1 <= x <= 10^9.💡 Core Algorithmic Approaches
- Removing elements from both ends leaves a contiguous subarray in the middle. So the task is to find the longest subarray whose sum equals
total - x. - If
total - x < 0, no answer exists; if it equals 0, the whole array must be removed. - Use a sliding window for the longest subarray with a given sum. All values are positive, so the window sum is monotone and two pointers work.
- The answer is
n - (longest subarray length).
💻 Benchmark Python3 Implementation
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
total = sum(nums)
target = total - x
if target < 0:
return -1
if target == 0:
return len(nums) # remove everything
l = 0
cur = 0
best = -1
for r, v in enumerate(nums):
cur += v
while cur > target and l <= r:
cur -= nums[l]
l += 1
if cur == target:
best = max(best, r - l + 1)
return len(nums) - best if best != -1 else -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass with a sliding window.
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Searching for the shortest prefix-plus-suffix directly: the complement formulation (longest middle subarray) is far simpler.
- Forgetting the
target == 0case: it means the entire array must be removed, and the sliding window would find an empty subarray of length 0 -- returningnis correct but should be explicit. - Using the window with negative values: the constraints guarantee positivity, which is what makes the two-pointer shrink valid.
- Returning
n - bestwhen no subarray matches:beststays -1 and the answer must be -1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner