# Minimum Operations to Reduce X to Zero
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-reduce-x-to-zero
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley)
---
## 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`. Note that this **modifies** the array for future operations.

Return _the **minimum number** of operations to reduce_ `x` _to **exactly**_ `0` _if it is possible_ _, otherwise, return_ `-1`.

**Example 1:**

**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.

**Example 2:**

**Input:** nums = [5,6,7,8,9], x = 4
**Output:** -1

**Example 3:**

**Input:** nums = [3,2,20,1,1,3], x = 10
**Output:** 5
**Explanation:** The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 104`
* `1 <= x <= 109`

# Approaches
## Brute Force Recursion
This approach directly simulates the problem statement. We can define a recursive function that explores every possible sequence of removing elements from either the left or the right end of the array. At each step, we have two choices: remove the leftmost element or the rightmost element. We explore both paths and continue until `x` becomes zero or it's impossible to reach zero.
**Time:** O(2^n), where n is the length of `nums`. For each element in the current subarray, we branch into two possibilities, leading to an exponential number of function calls. · **Space:** O(n), where n is the length of `nums`. This is due to the maximum depth of the recursion call stack.
**Pros:** Simple to understand as it directly models the process described in the problem.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error for all but the smallest inputs.; Performs a lot of redundant computations for the same subproblems.
### Explanation
The core idea is to use a recursive function, say `solve(left, right, x)`, which returns the minimum operations to make `x` zero using the subarray `nums[left...right]`. This method explores the entire decision tree of removals.

- **Base Cases:**
  - If `x == 0`, we've successfully reduced it to zero. No more operations are needed for this subproblem, so we return 0.
  - If `x < 0` or `left > right`, it's impossible to reach the target from this state. We return a value indicating impossibility, like `Integer.MAX_VALUE`.

- **Recursive Step:**
  - We make two recursive calls representing the two possible moves:
    1. Remove `nums[left]`: `1 + solve(left + 1, right, x - nums[left])`
    2. Remove `nums[right]`: `1 + solve(left, right - 1, x - nums[right])`
  - The function returns the minimum of these two results.

This approach is very slow because it recomputes results for the same subproblems multiple times and has an exponential number of paths to explore. Memoization is difficult because the state depends on `(left, right, x)`, and `x` can be large.

```java
// Note: This solution is for demonstration and will time out on larger test cases.
class Solution {
    public int minOperations(int[] nums, int x) {
        int result = solve(nums, x, 0, nums.length - 1);
        return result >= 1_000_000_000 ? -1 : result;
    }

    private int solve(int[] nums, int x, int left, int right) {
        if (x == 0) {
            return 0;
        }
        if (x < 0 || left > right) {
            return 1_000_000_000; // Using a large number for infinity
        }

        int takeLeft = 1 + solve(nums, x - nums[left], left + 1, right);
        int takeRight = 1 + solve(nums, x - nums[right], left, right - 1);

        return Math.min(takeLeft, takeRight);
    }
}
```
### Algorithm
- Define a recursive function `solve(nums, x, left, right)`.
- **Base Case 1:** If `x` is 0, a solution is found for the subproblem. Return 0 operations.
- **Base Case 2:** If `x` becomes negative or the pointers cross (`left > right`), this path is invalid. Return a very large number (infinity) to signify failure.
- **Recursive Step:** Explore two choices:
  1. Remove the leftmost element: `res1 = 1 + solve(nums, x - nums[left], left + 1, right)`.
  2. Remove the rightmost element: `res2 = 1 + solve(nums, x - nums[right], left, right - 1)`.
- Return the minimum of `res1` and `res2`.
- The initial call is `solve(nums, x, 0, nums.length - 1)`. If the result is infinity, it means no solution was found, so return -1.

## Prefix and Suffix Sums with Hashing
This approach considers the structure of the solution. Any valid set of operations involves removing a prefix of the array and a suffix of the array. We can precompute all possible suffix sums and store them in a hash map for quick lookups. Then, we iterate through all possible prefix sums and check if the remaining required sum exists in our suffix sum map.
**Time:** O(n). We iterate through the array twice: once to build the suffix sum map and once to check prefixes. Hash map operations take O(1) on average. · **Space:** O(n) in the worst case, to store all n possible suffix sums in the hash map.
**Pros:** Much more efficient than brute force, with a linear time complexity.; Guaranteed to find the optimal solution if one exists.
**Cons:** Requires extra space for the hash map, which can be up to O(n).
### Explanation
The problem is to find a prefix of length `i` and a suffix of length `j` such that their combined sum is `x`, and `i + j` is minimized. This can be solved by fixing one part (e.g., the prefix) and efficiently looking up the other (the suffix).

1.  First, we compute all possible sums that can be formed by taking elements from the suffix of the array. We store these sums and the number of elements taken (`j`) in a hash map: `map<sum, j>`. We also handle the case of taking 0 elements from the suffix (sum=0, j=0).
2.  Then, we iterate from the left of the array, calculating the prefix sum for taking `i` elements.
3.  For each prefix sum `p_sum`, we calculate the `target` sum needed from the suffix: `target = x - p_sum`.
4.  We check if this `target` exists in our suffix sum map.
5.  If it exists, we have a potential solution. The total number of operations is `i + j`, where `j` is the value from the map.
6.  We must also ensure that the prefix and suffix do not overlap. If we take `i` elements from the left (indices `0` to `i-1`) and `j` from the right (indices `n-j` to `n-1`), the condition `i-1 < n-j` or `i+j <= n` must hold.
7.  We keep track of the minimum number of operations found.

```java
class Solution {
    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        Map<Integer, Integer> suffixSumMap = new HashMap<>();
        suffixSumMap.put(0, 0); // sum 0 takes 0 elements
        int sum = 0;
        for (int i = n - 1; i >= 0; i--) {
            sum += nums[i];
            suffixSumMap.put(sum, n - i);
        }

        int minOps = Integer.MAX_VALUE;
        sum = 0;

        // Case: take 0 from prefix, all from suffix
        if (suffixSumMap.containsKey(x)) {
            minOps = suffixSumMap.get(x);
        }

        // Case: take i > 0 from prefix
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            int leftCount = i + 1;
            int target = x - sum;
            if (suffixSumMap.containsKey(target)) {
                int rightCount = suffixSumMap.get(target);
                if (leftCount + rightCount <= n) { // Ensure prefix and suffix don't overlap
                    minOps = Math.min(minOps, leftCount + rightCount);
                }
            }
        }

        return minOps == Integer.MAX_VALUE ? -1 : minOps;
    }
}
```
### Algorithm
- Create a hash map `suffixSumMap` to store `(sum, count)` pairs, where `sum` is the sum of a suffix and `count` is its length.
- Populate `suffixSumMap` by iterating from the end of `nums`. Also, add `(0, 0)` to handle cases where only a prefix is used.
- Initialize `minOps` to a very large value.
- Check if `x` itself is a valid suffix sum and update `minOps` if so.
- Iterate through `nums` from the beginning, calculating the `prefixSum` for the first `i` elements.
- For each `prefixSum`, calculate the required `target = x - prefixSum`.
- If `target` exists in `suffixSumMap`, let its count be `j`.
- Check for non-overlapping segments: if `i + j <= n`, we have a valid candidate. Update `minOps = min(minOps, i + j)`.
- After checking all prefixes, if `minOps` was updated, return it. Otherwise, return -1.

## Sliding Window on a Transformed Problem
This is the most optimal approach. The problem can be rephrased. Instead of finding the minimum number of elements to remove from the ends, we can find the maximum number of elements to *keep* in the middle. The elements we keep must form a contiguous subarray. The sum of this subarray must be `total_sum - x`. This transforms the problem into finding the longest subarray with a specific target sum, a classic problem solvable with a sliding window.
**Time:** O(n). The `right` pointer moves `n` times, and the `left` pointer also moves at most `n` times over the entire execution. Each element is visited at most twice. · **Space:** O(1). We only use a few variables to keep track of the window sum, pointers, and max length, regardless of the input size.
**Pros:** Most efficient solution in both time and space.; Solves the problem in a single pass over the array.; Requires no extra space proportional to the input size.
**Cons:** Relies on a clever transformation of the problem, which might not be immediately obvious.; The sliding window part only works because all numbers are positive. It would need modification for negative numbers.
### Explanation
The key insight is that the elements removed form a prefix and a suffix of the array. The elements that remain must therefore form a contiguous subarray in the middle.

- Let the total sum of all elements in `nums` be `totalSum`. If we remove elements summing to `x`, the remaining subarray must sum to `targetSum = totalSum - x`.
- Our goal is to minimize the number of removed elements, which is equivalent to maximizing the length of the remaining subarray.
- So, the problem becomes: "Find the longest contiguous subarray in `nums` that sums to `targetSum`".
- This can be solved efficiently using a sliding window approach, since all numbers in the array are positive.

```java
class Solution {
    public int minOperations(int[] nums, int x) {
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        long targetSum = totalSum - x;
        if (targetSum < 0) {
            return -1;
        }
        if (targetSum == 0) {
            return nums.length;
        }

        int n = nums.length;
        int maxLen = -1;
        long currentSum = 0;
        int left = 0;

        for (int right = 0; right < n; right++) {
            currentSum += nums[right];
            while (currentSum > targetSum && left <= right) {
                currentSum -= nums[left];
                left++;
            }
            if (currentSum == targetSum) {
                maxLen = Math.max(maxLen, right - left + 1);
            }
        }

        return maxLen == -1 ? -1 : n - maxLen;
    }
}
```
### Algorithm
- Calculate `totalSum` of all elements in `nums`.
- Define `targetSum = totalSum - x`. This is the sum of the subarray we want to keep.
- Handle edge cases:
  - If `targetSum < 0` (i.e., `x > totalSum`), it's impossible. Return -1.
  - If `targetSum == 0`, it means we must remove all elements. Return `n`.
- Initialize `maxLen = -1` (to track the max length of the subarray), `currentSum = 0`, and a left pointer `left = 0`.
- Iterate through `nums` with a right pointer `right` from 0 to `n-1`:
  - Add `nums[right]` to `currentSum` to expand the window.
  - While `currentSum > targetSum`, shrink the window from the left by subtracting `nums[left]` and incrementing `left`.
  - If `currentSum == targetSum`, we've found a valid subarray. Update `maxLen = max(maxLen, right - left + 1)`.
- After the loop, if `maxLen` is still -1, no solution exists. Return -1.
- Otherwise, the minimum operations is `n - maxLen`.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int[] nums, int x) {
    x = -x;
    for (int v : nums) {
      x += v;
    }
    Map<Integer, Integer> vis = new HashMap<>();
    vis.put(0, -1);
    int n = nums.length;
    int ans = 1 << 30;
    for (int i = 0, s = 0; i < n; ++i) {
      s += nums[i];
      vis.putIfAbsent(s, i);
      if (vis.containsKey(s - x)) {
        int j = vis.get(s - x);
        ans = Math.min(ans, n - (i - j));
      }
    }
    return ans == 1 << 30 ? -1 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums, int x) {
    x = accumulate(nums.begin(), nums.end(), 0) - x;
    unordered_map<int, int> vis{{0, -1}};
    int n = nums.size();
    int ans = 1 << 30;
    for (int i = 0, s = 0; i < n; ++i) {
      s += nums[i];
      if (!vis.count(s)) {
        vis[s] = i;
      }
      if (vis.count(s - x)) {
        int j = vis[s - x];
        ans = min(ans, n - (i - j));
      }
    }
    return ans == 1 << 30 ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int: x = sum(nums) - x vis = {0: - 1} ans = inf s, n = 0, len(nums) for i, v in enumerate(nums): s += v if s not in vis: vis[s] = i if s - x in vis: j = vis[s - x] ans = min(ans, n - (i - j)) return - 1 if ans == inf else ans

```