⚡Flashcard Drill➔
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

  1. 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.
  2. If total - x < 0, no answer exists; if it equals 0, the whole array must be removed.
  3. 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.
  4. 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 == 0 case: it means the entire array must be removed, and the sliding window would find an empty subarray of length 0 -- returning n is 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 - best when no subarray matches: best stays -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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems