Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1658. Minimum Operations to Reduce X to Zero - Leetcode Solution

Code Implementation

class Solution:
    def minOperations(self, nums, x):
        total = sum(nums)
        target = total - x
        n = len(nums)
        max_len = -1
        curr_sum = 0
        left = 0

        for right in range(n):
            curr_sum += nums[right]
            while left <= right and curr_sum > target:
                curr_sum -= nums[left]
                left += 1
            if curr_sum == target:
                max_len = max(max_len, right - left + 1)
        return n - max_len if max_len != -1 else -1
      
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        int target = total - x;
        int n = nums.size(), maxLen = -1;
        int currSum = 0, left = 0;
        for (int right = 0; right < n; ++right) {
            currSum += nums[right];
            while (left <= right && currSum > target) {
                currSum -= nums[left];
                left++;
            }
            if (currSum == target) {
                maxLen = max(maxLen, right - left + 1);
            }
        }
        return maxLen == -1 ? -1 : n - maxLen;
    }
};
      
class Solution {
    public int minOperations(int[] nums, int x) {
        int total = 0;
        for (int num : nums) total += num;
        int target = total - x;
        int n = nums.length;
        int maxLen = -1, currSum = 0, left = 0;
        for (int right = 0; right < n; right++) {
            currSum += nums[right];
            while (left <= right && currSum > target) {
                currSum -= nums[left];
                left++;
            }
            if (currSum == target) {
                maxLen = Math.max(maxLen, right - left + 1);
            }
        }
        return maxLen == -1 ? -1 : n - maxLen;
    }
}
      
var minOperations = function(nums, x) {
    let total = nums.reduce((a, b) => a + b, 0);
    let target = total - x;
    let n = nums.length;
    let maxLen = -1, currSum = 0, left = 0;
    for (let right = 0; right < n; right++) {
        currSum += nums[right];
        while (left <= right && currSum > target) {
            currSum -= nums[left];
            left++;
        }
        if (currSum === target) {
            maxLen = Math.max(maxLen, right - left + 1);
        }
    }
    return maxLen === -1 ? -1 : n - maxLen;
};

Problem Description

Given an array of integers nums and an integer x, your goal is to reduce x to exactly zero by removing elements from either the start or the end of the array (you can remove from either side in any order). Each removal subtracts the value of the removed element from x. Return the minimum number of operations (removals) needed to reduce x to zero, or -1 if it is not possible. Each element in nums can be removed at most once (no reuse).

Thought Process

At first glance, the problem looks like it requires trying all possible combinations of removing numbers from the left and right to reach x. This brute-force approach would be very slow, especially for large arrays. Instead, we look for a pattern: since we can only remove from the ends, every solution is a combination of some prefix (from the left) and some suffix (from the right) whose sum equals x. But checking all such combinations is still inefficient.

A key insight is to flip the problem: instead of selecting elements that sum to x from the ends, what if we try to find the longest subarray in the middle whose sum is total - x, where total is the sum of all elements? If we can find such a subarray, then the elements we remove from the ends are exactly those not in the subarray. Thus, the minimum number of operations is the total array length minus the length of this subarray.

Solution Approach

We solve the problem efficiently using the sliding window technique:
  • First, compute the sum of all elements in nums and call it total.
  • Our new target is total - x. We look for the longest contiguous subarray whose sum is exactly this target.
  • We use two pointers (left and right) to define a window, and a running sum (curr_sum) of the current window.
  • We expand the window by moving right forward and adding nums[right] to curr_sum.
  • If curr_sum exceeds target, we shrink the window from the left by moving left forward and subtracting nums[left] from curr_sum.
  • Whenever curr_sum equals target, we update the maximum window size found so far.
  • Finally, if a valid window was found, the answer is len(nums) - max_window_size. If not, return -1.
We use a sliding window because all numbers are positive, so the sum of any window increases as we move right forward, and only decreases as we move left forward. This makes the algorithm efficient and avoids checking all possible subarrays.

Example Walkthrough

Let's consider nums = [1,1,4,2,3] and x = 5.
  • First, total = 1 + 1 + 4 + 2 + 3 = 11.
  • So, target = total - x = 11 - 5 = 6.
  • We look for the longest subarray that sums to 6.
  • Sliding window steps:
    • Start: curr_sum = 0, left = 0
    • right = 0: curr_sum = 1
    • right = 1: curr_sum = 2
    • right = 2: curr_sum = 6 (found window [0,2])
    • Update max_len = 3
    • right = 3: curr_sum = 8 (exceeds target, move left)
    • Subtract nums[0]: curr_sum = 7
    • Subtract nums[1]: curr_sum = 6 (window [2,3])
    • max_len remains 3 (window size is 2)
    • right = 4: curr_sum = 9 (exceeds target, move left)
    • Subtract nums[2]: curr_sum = 5
  • Longest subarray with sum 6 is length 3. So, answer is 5 - 3 = 2.
  • This matches the answer: remove nums[0] and nums[1] (or nums[4] and nums[3]) to sum to 5.

Time and Space Complexity

  • Brute-force approach: Checking all combinations of prefix and suffix sums takes O(N2) time, which is inefficient for large arrays.
  • Optimized approach (sliding window):
    • Time Complexity: O(N), because each element is visited at most twice (once when expanding the window, once when shrinking).
    • Space Complexity: O(1), since we only use a few variables for tracking sums and pointers, not extra data structures proportional to input size.

Summary

The problem is elegantly solved by transforming it into finding the longest subarray whose sum is total - x. This allows us to use an efficient sliding window technique, avoiding brute-force checks of all combinations. The solution is both efficient and clever, leveraging properties of array sums and the constraints of the problem. This approach is a good example of how reframing a problem can lead to a much simpler and faster solution.