1658. Minimum Operations to Reduce X to Zero

The 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 <= 10⁵
1 <= nums[i] <= 10⁴
1 <= x <= 10⁹

Approach overview

Problem Overview: You are given an array nums and an integer x. In one operation you remove the leftmost or rightmost element from the array and subtract its value from x. The goal is to reduce x to exactly zero using the minimum number of operations.

The key observation: removing elements from both ends is equivalent to keeping a contiguous middle subarray. If the total sum of the array is total, the removed elements must sum to x, meaning the remaining subarray must sum to total - x. The task becomes finding the longest subarray with that sum.

Approach 1: Sliding Window for the Complement (O(n) time, O(1) space)

This is the optimal approach and the one most interviewers expect. First compute target = totalSum - x. Instead of thinking about removing elements, search for the longest subarray whose sum equals target. Use a classic sliding window with two pointers. Expand the right pointer while accumulating the window sum, and shrink the left pointer whenever the sum exceeds the target. When the window sum equals the target, record the maximum length. If the longest valid subarray length is L, the minimum operations equals n - L. This works because all values are positive, allowing the window to move monotonically.

Approach 2: Prefix Sum + Hash Table (O(n) time, O(n) space)

Another way to find the longest subarray with sum target uses prefix sums and a hash table. Maintain a running prefix sum while iterating through the array. Store the earliest index where each prefix sum appears. If the current prefix sum is curr, check whether curr - target exists in the map. If it does, the elements between those indices form a valid subarray with the desired sum. Track the maximum length seen. This approach works for more general arrays but uses extra memory for the hash map.

Approach 3: Dynamic Programming (O(n * x) time, O(x) space)

A dynamic programming formulation treats the problem as choosing elements from the left or right to reach sum x. Define dp[s] as the minimum operations needed to reach sum s. Iteratively update states as you consider elements from both ends. While this approach demonstrates the problem’s combinational nature, it becomes inefficient when x is large. For typical constraints, the sliding window strategy is significantly faster and simpler.

Recommended for interviews: The sliding window complement trick is the expected solution. It reduces the original problem to a longest subarray search in O(n) time and constant space. Mentioning the prefix-sum alternative shows broader understanding, while the sliding window demonstrates strong problem transformation skills.

Approach 1: Sliding Window for the Complement

To make the problem simpler, we first calculate the total sum of the array, and then look for the longest subarray whose sum is equal to totalSum - x. This is because removing elements to get a sum of x is equivalent to finding a subarray with this complementary sum.

If we find this subarray, the number of operations is the total length of the array minus the length of this subarray. We use a sliding window to find the longest subarray with the target sum.

Python

from typing import List

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        totalSum = sum(nums)
        target = totalSum - x
        if target < 0:
            return -1

        left, currSum, maxLength = 0, 0, -1
        for right in range(len(nums)):
            currSum += nums[right]

            while currSum > target and left <= right:
                currSum -= nums[left]
                left += 1

            if currSum == target:
                maxLength = max(maxLength, right - left + 1)

        return -1 if maxLength == -1 else len(nums) - maxLength

Java

import java.util.*;

class Solution {
    public int minOperations(int[] nums, int x) {
        int totalSum = Arrays.stream(nums).sum();
        int target = totalSum - x;
        if (target < 0) return -1;

        int left = 0, currSum = 0, maxLength = -1;
        for (int right = 0; right < nums.length; ++right) {
            currSum += nums[right];

            while (currSum > target && left <= right) {
                currSum -= nums[left];
                ++left;
            }

            if (currSum == target) {
                maxLength = Math.max(maxLength, right - left + 1);
            }
        }

        return maxLength == -1 ? -1 : nums.length - maxLength;
    }
}

C++

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        int target = totalSum - x;
        if (target < 0) return -1;

        int left = 0, currSum = 0, maxLength = -1;
        for (int right = 0; right < nums.size(); ++right) {
            currSum += nums[right];

            while (currSum > target && left <= right) {
                currSum -= nums[left];
                ++left;
            }

            if (currSum == target) {
                maxLength = max(maxLength, right - left + 1);
            }
        }

        return maxLength == -1 ? -1 : nums.size() - maxLength;
    }
};

JavaScript

var minOperations = function(nums, x) {
    let totalSum = nums.reduce((a, b) => a + b, 0);
    let target = totalSum - x;
    if (target < 0) return -1;

    let left = 0, currSum = 0, maxLength = -1;
    for (let right = 0; right < nums.length; ++right) {
        currSum += nums[right];

        while (currSum > target && left <= right) {
            currSum -= nums[left];
            left++;
        }

        if (currSum == target) {
            maxLength = Math.max(maxLength, right - left + 1);
        }
    }

    return maxLength === -1 ? -1 : nums.length - maxLength;
};

#include <stdio.h>

int minOperations(int* nums, int numsSize, int x){
    int totalSum = 0;
    for (int i = 0; i < numsSize; ++i) totalSum += nums[i];
    int target = totalSum - x;
    if (target < 0) return -1;

    int left = 0, right = 0, currSum = 0, maxLength = -1;
    while (right < numsSize) {
        currSum += nums[right++];

        while (currSum > target && left < right) {
            currSum -= nums[left++];
        }

        if (currSum == target) {
            maxLength = (maxLength > right - left) ? maxLength : right - left;
        }
    }

    return maxLength == -1 ? -1 : numsSize - maxLength;
}

using System;

public class Solution {
    public int MinOperations(int[] nums, int x) {
        int totalSum = 0;
        foreach (var num in nums) totalSum += num;

        int target = totalSum - x;
        if (target < 0) return -1;

        int left = 0, currSum = 0, maxLength = -1;
        for (int right = 0; right < nums.Length; ++right) {
            currSum += nums[right];

            while (currSum > target && left <= right) {
                currSum -= nums[left];
                left++;
            }

            if (currSum == target) {
                maxLength = Math.Max(maxLength, right - left + 1);
            }
        }

        return maxLength == -1 ? -1 : nums.Length - maxLength;
    }
}

The Python solution leverages a sliding window with pointers left and right to calculate the necessary subarray's length. The subarray that complements x in total sum is sought to minimize operations.

Complexity

Time Complexity: O(n), where n is the length of the array.

Space Complexity: O(1) for extra variable storage.

Try this approach in the editor

Approach 2: Dynamic Programming

This alternative method uses dynamic programming to explore all possible choices at any instance, storing results for optimal decisions. We define a DP array dp[i] that represents the minimum operations needed to reduce x using the first i elements from either side. We initialize by removing elements and updating DP states iteratively.

We optimize storage by using only needed previous state references, ensuring computations are rapid and effective. This dynamic programming approach is relatively complex due to combination subproblems hence less preferable but a dividing strategy worth studying.

Python

from typing import List

def minOperations(nums: List[int], x: int) -> int:
    n = len(nums)
    totalSum = sum(nums)
    target = totalSum - x

    if target < 0:
        return -1

    # DP Table
    dp = [-1] * (target + 1)
    dp[0] = 0

    for num in nums:
        for curr in range(target, num - 1, -1):
            if dp[curr - num] != -1:
                dp[curr] = max(dp[curr], dp[curr - num] + 1)

    return n - dp[target] if dp[target] != -1 else -1

The Python solution leverages dynamic programming using a 1D array. As we iterate through nums, each element influences potential sums achievable by contributing to subsets, thus establishing a table of values dp representing the maximum number achieved at every potential sum. The solution emerges when final target accessibility is evaluated post iterations.

Complexity

Time Complexity: O(n*m), where n is the total number and m denotes max target value.

Space Complexity: O(m) in size for storage structures.

Try this approach in the editor

Approach 3: Hash Table + Prefix Sum

According to the problem description, we need to remove elements from both ends of the array nums so that the sum of the removed elements equals x, and the number of removed elements is minimized. We can transform the problem into: find the longest consecutive subarray in the array nums such that the sum of the subarray s = sum_{i=0}^{n} nums[i] - x. In this way, we can transform the problem into finding the length mx of the longest consecutive subarray in the array nums with a sum of s, and the answer is n - mx.

We initialize mx = -1, and then use a hash table vis to store the prefix sum, where the key is the prefix sum and the value is the index corresponding to the prefix sum.

Traverse the array nums, for the current element nums[i], calculate the prefix sum t, if t is not in the hash table, add t to the hash table; if t - s is in the hash table, update mx = max(mx, i - vis[t - s]).

Finally, if mx = -1, return -1, otherwise return n - mx.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.

TypeScript

function minOperations(nums: number[], x: number): number {
    const s = nums.reduce((acc, cur) => acc + cur, -x);
    const vis: Map<number, number> = new Map([[0, -1]]);
    let [mx, t] = [-1, 0];
    const n = nums.length;
    for (let i = 0; i < n; ++i) {
        t += nums[i];
        if (!vis.has(t)) {
            vis.set(t, i);
        }
        if (vis.has(t - s)) {
            mx = Math.max(mx, i - vis.get(t - s)!);
        }
    }
    return ~mx ? n - mx : -1;
}

func minOperations(nums []int, x int) int {
	s := -x
	for _, v := range nums {
		s += v
	}
	vis := map[int]int{0: -1}
	mx, t := -1, 0
	for i, v := range nums {
		t += v
		if _, ok := vis[t]; !ok {
			vis[t] = i
		}
		if j, ok := vis[t-s]; ok {
			mx = max(mx, i-j)
		}
	}
	if mx == -1 {
		return -1
	}
	return len(nums) - mx
}

Rust

use std::collections::HashMap;

impl Solution {
    pub fn min_operations(nums: Vec<i32>, x: i32) -> i32 {
        let s = nums.iter().sum::<i32>() - x;
        let mut vis: HashMap<i32, i32> = HashMap::new();
        vis.insert(0, -1);
        let mut mx = -1;
        let mut t = 0;
        for (i, v) in nums.iter().enumerate() {
            t += v;
            if !vis.contains_key(&t) {
                vis.insert(t, i as i32);
            }
            if let Some(&j) = vis.get(&(t - s)) {
                mx = mx.max((i as i32) - j);
            }
        }
        if mx == -1 {
            -1
        } else {
            (nums.len() as i32) - mx
        }
    }
}

Try this approach in the editor

Approach 4: Two Pointers

Based on the analysis of Solution 1, we need to find the length mx of the longest consecutive subarray in the array nums with a sum of s. Since all elements in the array nums are positive integers, the prefix sum of the array will only increase monotonically, so we can use two pointers to solve this problem.

We initialize pointer j = 0, prefix sum t = 0, and the length of the longest consecutive subarray mx = -1.

Traverse the array nums, for the current element nums[i], calculate the prefix sum t += nums[i]. If t > s, then move the pointer j until t leq s. If t = s, then update mx = max(mx, i - j + 1).

Finally, if mx = -1, return -1, otherwise return n - mx.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

TypeScript

function minOperations(nums: number[], x: number): number {
    const s = nums.reduce((acc, cur) => acc + cur, -x);
    let [mx, t] = [-1, 0];
    const n = nums.length;
    for (let i = 0, j = 0; i < n; ++i) {
        t += nums[i];
        while (t > s) {
            t -= nums[j++];
        }
        if (t === s) {
            mx = Math.max(mx, i - j + 1);
        }
    }
    return ~mx ? n - mx : -1;
}

func minOperations(nums []int, x int) int {
	s := -x
	for _, v := range nums {
		s += v
	}
	mx, t, j := -1, 0, 0
	for i, v := range nums {
		t += v
		for ; j <= i && t > s; j++ {
			t -= nums[j]
		}
		if t == s {
			mx = max(mx, i-j+1)
		}
	}
	if mx == -1 {
		return -1
	}
	return len(nums) - mx
}

Rust

impl Solution {
    pub fn min_operations(nums: Vec<i32>, x: i32) -> i32 {
        let s: i32 = nums.iter().sum::<i32>() - x;
        let mut j: usize = 0;
        let mut t: i32 = 0;
        let mut mx: i32 = -1;
        for (i, &v) in nums.iter().enumerate() {
            t += v;
            while j <= i && t > s {
                t -= nums[j];
                j += 1;
            }
            if t == s {
                mx = mx.max((i - j + 1) as i32);
            }
        }
        if mx == -1 {
            -1
        } else {
            (nums.len() as i32) - mx
        }
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sliding Window for the Complement	Time Complexity: O(n), where n is the length of the array. Space Complexity: O(1) for extra variable storage.
Dynamic Programming	Time Complexity: O(n*m), where n is the total number and m denotes max target value. Space Complexity: O(m) in size for storage structures.
Hash Table + Prefix Sum	–
Two Pointers	–

Complexity analysis

Approach	Time	Space	When to Use
Sliding Window (Complement Subarray)	O(n)	O(1)	Best choice when array values are positive and you need the optimal interview solution
Prefix Sum + Hash Map	O(n)	O(n)	General technique for longest subarray with given sum
Dynamic Programming	O(n * x)	O(x)	Useful for conceptual understanding when modeling choices from both ends

Frequently asked questions

Is Minimum Operations to Reduce X to Zero easy or hard?

Minimum Operations to Reduce X to Zero is rated Medium difficulty on LeetCode with about a 40% acceptance rate. The challenge is recognizing that removing elements from the ends can be reframed as finding the longest subarray with a specific sum.

How to solve Minimum Operations to Reduce X to Zero in O(n)?

First compute totalSum of the array and set target = totalSum - x. Use a sliding window to find the longest contiguous subarray with sum equal to target. If the maximum length of such a subarray is L, the minimum operations required is n - L.

What is the best approach for Minimum Operations to Reduce X to Zero?

The optimal approach uses a sliding window to find the longest subarray whose sum equals totalSum - x. Instead of removing elements from both ends, you keep the largest middle subarray and remove the rest. This runs in O(n) time and O(1) space, making it the most efficient solution.

What data structure is used in Minimum Operations to Reduce X to Zero?

The optimal solution primarily uses the sliding window technique on an array. An alternative implementation uses a hash table with prefix sums to track previous cumulative sums and detect valid subarrays.

What is the time complexity of Minimum Operations to Reduce X to Zero?

The optimal sliding window solution runs in O(n) time because each element is processed at most twice by the two pointers. Space complexity is O(1). A prefix-sum + hash map variant also runs in O(n) time but uses O(n) extra space.

Minimum Operations to Reduce X to Zero Python or Java solution approach?

Both Python and Java implementations typically use the sliding window complement approach. Compute target = totalSum - x, move two pointers across the array, maintain the window sum, and track the longest valid window to derive the minimum operations.

Is Minimum Operations to Reduce X to Zero asked at Google, Amazon, or Meta?

Minimum Operations to Reduce X to Zero appears frequently in interview preparation lists for companies like Amazon, Google, and Meta because it tests sliding window reasoning and problem transformation using prefix sums.

Minimum Operations to Reduce X to Zero solution and explanation

The problem

Approach overview

Approach 1: Sliding Window for the Complement

Approach 2: Dynamic Programming

Approach 3: Hash Table + Prefix Sum

Approach 4: Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Operations to Reduce X to Zero solution and explanation

The problem

Approach overview

Approach 1: Sliding Window for the Complement

Approach 2: Dynamic Programming

Approach 3: Hash Table + Prefix Sum

Approach 4: Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems