Minimum Operations to Reduce X to Zero

medium sliding window prefix sum

Problem

You have an array of positive integers nums and an integer x. In one operation you may remove either the leftmost or the rightmost element of the array and subtract its value from x. Find the smallest number of operations that brings x exactly to 0, or return −1 if no combination of edge removals can do it.

Inputnums = [1,1,4,2,3], x = 5

Output2

Removing the last two elements (3, then 2) subtracts exactly 5 from x, so 2 operations suffice.

nums (comma-separated positive integers)

def min_operations(nums, x):
    target = sum(nums) - x
    if target < 0:
        return -1
    if target == 0:
        return len(nums)
    best = -1
    cur = 0
    left = 0
    for right in range(len(nums)):
        cur += nums[right]
        while cur > target:
            cur -= nums[left]
            left += 1
        if cur == target:
            best = max(best, right - left + 1)
    return -1 if best < 0 else len(nums) - best

function minOperations(nums, x) {
  const target = nums.reduce((a, b) => a + b, 0) - x;
  if (target < 0) return -1;
  if (target === 0) return nums.length;
  let best = -1, cur = 0, left = 0;
  for (let right = 0; right < nums.length; right++) {
    cur += nums[right];
    while (cur > target) {
      cur -= nums[left];
      left++;
    }
    if (cur === target) {
      best = Math.max(best, right - left + 1);
    }
  }
  return best < 0 ? -1 : nums.length - best;
}

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

int minOperations(vector<int>& nums, int x) {
    long target = accumulate(nums.begin(), nums.end(), 0L) - x;
    if (target < 0) return -1;
    if (target == 0) return nums.size();
    int best = -1, left = 0;
    long cur = 0;
    for (int right = 0; right < (int)nums.size(); right++) {
        cur += nums[right];
        while (cur > target) {
            cur -= nums[left];
            left++;
        }
        if (cur == target) {
            best = max(best, right - left + 1);
        }
    }
    return best < 0 ? -1 : (int)nums.size() - best;
}

Explanation

The trick is to flip the problem. Removing elements from both ends to make their values sum to x is the same as keeping a contiguous middle subarray whose sum is total − x. Minimizing removals therefore means maximizing the length of that kept middle, and the answer is n − best where best is the longest middle's length.

Because every element is positive, a subarray's sum strictly grows as it extends and strictly shrinks as it loses elements. That monotonicity is exactly what a sliding window needs: grow the window by moving right, and whenever the running sum cur overshoots target, shrink from left until it no longer does. Each time cur == target, record the window length.

Two edge cases come first. If target = total − x is negative, even removing the entire array cannot subtract enough, so return −1. If target is 0, we must remove everything, so the answer is n.

Walk through the default example nums = [1,1,4,2,3], x = 5: total = 11, so target = 6. Expanding right gives sums 1, 2, 6 — a hit at window [0..2] of length 3. Adding 2 makes 8, shrinking twice leaves [2..3] with sum 6 (length 2, no improvement). Adding 3 makes 9, one shrink leaves sum 5. The best kept middle has length 3, so the answer is 5 − 3 = 2.

Each index enters the window once when right passes it and leaves at most once when left passes it, so the total work is linear: O(n) time. Only a handful of counters are kept, so the extra space is O(1).

Time: O(n) Space: O(1)