355. Minimum Operations to Reduce X to Zero

Removing a prefix and a suffix that together sum to x is the same as keeping a contiguous middle block that sums to total - x. So instead of minimizing the elements removed, maximize the length of a middle subarray whose sum equals total - x; the answer is n minus that length. Because every value is positive, a sliding window finds the longest such subarray in one pass.

Reframing the problem

Every operation removes an element from the left end or the right end. So after all operations, the elements you removed form a prefix plus a suffix, and the elements you kept form a contiguous middle block.

You want the removed prefix + suffix to sum to exactly x. Let total = sum(nums). If the removed part sums to x, then the kept middle block sums to total - x. Minimizing the number of removed elements is the same as maximizing the length of the kept middle block.

So the problem becomes: find the longest contiguous subarray whose sum equals target = total - x. If its length is L, the answer is n - L.

Why a sliding window works

All values are positive, so extending a window on the right only increases its sum and shrinking on the left only decreases it. That monotonicity lets us keep a window whose sum never exceeds target, growing right and shrinking left, and record the widest window that hits target exactly.

Algorithm

1. Compute target = total - x.
2. If target < 0, even removing everything can't reach x → return -1.
3. If target == 0, the whole array must be removed → return n.
4. Slide a window [left..right] with running sum cur:
   • add nums[right];
   • while cur > target, drop nums[left] and advance left;
   • whenever cur == target, update best = max(best, right - left + 1).
5. Return n - best if any window matched, else -1.

Worked example: nums = [1,1,4,2,3], x = 5

total = 11, so target = 11 - 5 = 6. We look for the longest subarray summing to 6.

The longest middle block summing to 6 has length 3 ([1,1,4]), so the answer is 5 - 3 = 2 — remove the last two elements 2 and 3.

Complexity

• Time: O(n) — each index enters and leaves the window at most once.
• Space: O(1).

class Solution {
    public int minOperations(int[] nums, int x) {
        long target = 0;
        for (int v : nums) target += v;
        target -= x;
        if (target < 0) return -1;
        if (target == 0) return nums.length;
        int left = 0, best = -1;
        long cur = 0;
        for (int right = 0; right < nums.length; right++) {
            cur += nums[right];
            while (cur > target && left <= right) {
                cur -= nums[left];
                left++;
            }
            if (cur == target) {
                best = Math.max(best, right - left + 1);
            }
        }
        return best == -1 ? -1 : nums.length - best;
    }
}