LeetCode 1658 - Minimum Operations to Reduce X to Zero

LeetCode Problem 1658

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Sliding Window, Prefix Sum

Solution

Problem Understanding

The problem gives us an integer array nums and a target integer x. In one operation, we are allowed to remove either the leftmost element or the rightmost element from the array. Whenever we remove a value, we subtract it from x.

Our goal is to reduce x to exactly 0 using the minimum number of removals. If it is impossible to make x exactly 0, we return -1.

The important detail is that we can only remove elements from the two ends of the array. We are not allowed to remove arbitrary middle elements. Every removal changes the remaining array for future operations.

For example, if:

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

We can remove the rightmost 3, then the new array becomes [1,1,4,2] and x becomes 2. Then remove the rightmost 2, making x = 0. That takes 2 operations.

The constraints are important:

• nums.length can be as large as 10^5
• Each element can be up to 10^4
• x can be as large as 10^9

These constraints immediately tell us that quadratic solutions will be too slow. Any algorithm close to O(n^2) will likely time out for arrays of size 100000. We should aim for an O(n) or O(n log n) solution.

There are several important edge cases to consider:

• x may be larger than the total sum of the array, making the answer impossible.
• The optimal solution may require removing all elements.
• There may be multiple valid ways to reduce x to zero, and we must choose the one with the fewest operations.
• The array contains only positive integers, which is extremely important because it enables the sliding window optimization.
• A naive greedy strategy can fail because locally optimal removals may prevent a globally optimal answer.

Approaches

Brute Force Approach

A straightforward idea is to try every possible combination of removing elements from the left and right sides.

Suppose we remove i elements from the left and j elements from the right. We can compute whether those removed elements sum to x. If they do, then the number of operations is i + j.

To implement this, we could:

1. Precompute prefix sums from the left.
2. Precompute suffix sums from the right.
3. Try every possible split between left removals and right removals.

This works because every valid solution corresponds to some combination of left and right removals.

However, if implemented naively, this can require checking many combinations. A pure brute force method would examine all pairs (i, j), leading to O(n^2) time complexity, which is too slow for n = 100000.

Key Insight

Instead of thinking about which elements we remove, we can think about which elements remain.

If the total sum of the array is:

totalSum

and we remove elements summing to x, then the remaining middle subarray must sum to:

target = totalSum - x

So the problem becomes:

Find the longest contiguous subarray whose sum equals target.

Why longest?

Because every element not in that subarray must be removed. If the remaining subarray is as long as possible, then the number of removed elements is minimized.

This transformation completely changes the problem into a classic sliding window problem.

Since all numbers are positive, the sliding window technique works perfectly:

• If the current window sum is too small, expand the window.
• If the current window sum is too large, shrink the window.
• Whenever the sum equals target, update the maximum subarray length.

Finally:

minimum operations = n - longestSubarrayLength

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) or O(n)	Tries combinations of left and right removals
Optimal Sliding Window	O(n)	O(1)	Finds longest subarray with sum totalSum - x

Algorithm Walkthrough

Optimal Sliding Window Algorithm

1. Compute the total sum of the array.

We first calculate:

totalSum = sum(nums)

This tells us how much value exists in the entire array. 2. Compute the target subarray sum.

Since removed elements must sum to x, the remaining subarray must sum to:

target = totalSum - x

3. Handle impossible cases early.

If target < 0, then x is larger than the total array sum, so it is impossible to reduce x to zero.

Return -1. 4. Handle the case where the entire array must be removed.

If target == 0, then the only solution is removing every element.

Return len(nums). 5. Initialize the sliding window.

We maintain:

• left, the start of the window
• currentSum, the sum of the current window
• maxLength, the length of the longest valid subarray found so far

6. Expand the window using the right pointer.

For each right index:

• Add nums[right] to currentSum.

7. Shrink the window when necessary.

Since all numbers are positive, if currentSum > target, the only way to reduce the sum is to move the left pointer forward.

While:

currentSum > target

subtract nums[left] and increment left. 8. Check for valid windows.

Whenever:

currentSum == target

we found a valid remaining subarray.

Update:

maxLength = max(maxLength, right - left + 1)

9. Compute the answer.

If no valid subarray exists, return -1.

Otherwise:

answer = len(nums) - maxLength

Why it works

Every valid sequence of removals leaves behind a contiguous middle subarray. The sum of that remaining subarray must equal totalSum - x.

Therefore, minimizing removals is equivalent to maximizing the size of the remaining subarray.

Because all numbers are positive, the sliding window always moves monotonically forward. Once the window sum exceeds the target, shrinking from the left is guaranteed to decrease the sum. This property ensures the algorithm checks every valid window efficiently in linear time.

Python Solution

from typing import List

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        total_sum = sum(nums)
        target = total_sum - x

        if target < 0:
            return -1

        if target == 0:
            return len(nums)

        left = 0
        current_sum = 0
        max_length = -1

        for right in range(len(nums)):
            current_sum += nums[right]

            while current_sum > target:
                current_sum -= nums[left]
                left += 1

            if current_sum == target:
                window_length = right - left + 1
                max_length = max(max_length, window_length)

        if max_length == -1:
            return -1

        return len(nums) - max_length

The implementation begins by calculating the total array sum and deriving the target sum for the remaining subarray.

The two early return conditions simplify important edge cases:

• If target < 0, the array does not contain enough total value.
• If target == 0, every element must be removed.

The sliding window uses two pointers:

• left
• right

The right pointer expands the window, while the left pointer shrinks it whenever the sum becomes too large.

Because all values are positive, the window sum changes predictably:

• Expanding increases the sum.
• Shrinking decreases the sum.

This property guarantees correctness and linear complexity.

Whenever the current window sum matches the target, we compute the window length and update the maximum valid subarray length.

Finally, we subtract that maximum length from the total array size to determine how many elements must be removed.

Go Solution

func minOperations(nums []int, x int) int {
    totalSum := 0

    for _, num := range nums {
        totalSum += num
    }

    target := totalSum - x

    if target < 0 {
        return -1
    }

    if target == 0 {
        return len(nums)
    }

    left := 0
    currentSum := 0
    maxLength := -1

    for right := 0; right < len(nums); right++ {
        currentSum += nums[right]

        for currentSum > target {
            currentSum -= nums[left]
            left++
        }

        if currentSum == target {
            windowLength := right - left + 1

            if windowLength > maxLength {
                maxLength = windowLength
            }
        }
    }

    if maxLength == -1 {
        return -1
    }

    return len(nums) - maxLength
}

The Go implementation follows the same logic as the Python version.

One difference is that Go does not provide built in functions like sum(), so we manually compute the total array sum using a loop.

Go slices are used directly without needing any special handling for empty arrays because the constraints guarantee at least one element.

Integer overflow is not an issue because the maximum possible total sum is:

10^5 * 10^4 = 10^9

which fits safely within Go's standard int type on LeetCode environments.

Worked Examples

Example 1

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

First compute:

totalSum = 11
target = 11 - 5 = 6

Now we find the longest subarray with sum 6.

Right	Added Value	Current Window	Current Sum	Action	Max Length
0	1	[1]	1	Expand	-1
1	1	[1,1]	2	Expand	-1
2	4	[1,1,4]	6	Valid window	3
3	2	[1,1,4,2]	8	Shrink left	3
3	2	[1,4,2]	7	Shrink left	3
3	2	[4,2]	6	Valid window	3
4	3	[4,2,3]	9	Shrink left	3
4	3	[2,3]	5	Continue	3

Longest valid subarray length is 3.

Therefore:

operations = 5 - 3 = 2

Example 2

nums = [5,6,7,8,9]
x = 4

Compute:

totalSum = 35
target = 31

No contiguous subarray sums to 31.

Therefore:

return -1

Example 3

nums = [3,2,20,1,1,3]
x = 10

Compute:

totalSum = 30
target = 20

We search for the longest subarray summing to 20.

Right	Window	Sum	Max Length
0	[3]	3	-1
1	[3,2]	5	-1
2	[3,2,20]	25	Shrink
2	[2,20]	22	Shrink
2	[20]	20	1
3	[20,1]	21	Shrink
4	[1,1]	2	1
5	[1,1,3]	5	1

Longest valid subarray length is 1.

Therefore:

operations = 6 - 1 = 5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each pointer moves through the array at most once
Space	O(1)	Only a few variables are used

The sliding window is efficient because both pointers move strictly forward. The right pointer visits each element once, and the left pointer also advances at most n times total.

No additional data structures proportional to input size are required, so the space complexity remains constant.

Test Cases

from typing import List

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        total_sum = sum(nums)
        target = total_sum - x

        if target < 0:
            return -1

        if target == 0:
            return len(nums)

        left = 0
        current_sum = 0
        max_length = -1

        for right in range(len(nums)):
            current_sum += nums[right]

            while current_sum > target:
                current_sum -= nums[left]
                left += 1

            if current_sum == target:
                max_length = max(max_length, right - left + 1)

        if max_length == -1:
            return -1

        return len(nums) - max_length

solution = Solution()

assert solution.minOperations([1, 1, 4, 2, 3], 5) == 2
# standard example with optimal right removals

assert solution.minOperations([5, 6, 7, 8, 9], 4) == -1
# impossible target

assert solution.minOperations([3, 2, 20, 1, 1, 3], 10) == 5
# removals from both sides

assert solution.minOperations([1, 1], 3) == -1
# x larger than total sum

assert solution.minOperations([5], 5) == 1
# single element exact match

assert solution.minOperations([1, 2, 3], 6) == 3
# must remove entire array

assert solution.minOperations([1, 2, 3, 4, 5], 5) == 1
# remove single right element

assert solution.minOperations([5, 1, 2, 3, 4], 5) == 1
# remove single left element

assert solution.minOperations([1, 1, 1, 1, 1], 3) == 3
# many equivalent solutions

assert solution.minOperations([10, 1, 1, 1, 1], 10) == 1
# optimal solution at boundary

assert solution.minOperations([1, 2, 3, 4, 5], 15) == 5
# remove everything

Test Summary

Test	Why
[1,1,4,2,3], x=5	Standard example
[5,6,7,8,9], x=4	Impossible case
[3,2,20,1,1,3], x=10	Requires removals from both ends
[1,1], x=3	x larger than total sum
[5], x=5	Single element solution
[1,2,3], x=6	Entire array removed
[1,2,3,4,5], x=5	Right boundary removal
[5,1,2,3,4], x=5	Left boundary removal
[1,1,1,1,1], x=3	Multiple equivalent solutions
[10,1,1,1,1], x=10	Large boundary value
[1,2,3,4,5], x=15	Full array exact sum

Edge Cases

One important edge case occurs when x is larger than the total array sum. In this situation, it is mathematically impossible to remove enough value to reduce x to zero. A buggy implementation might continue searching unnecessarily or produce an invalid answer. The implementation avoids this by immediately checking whether target < 0.

Another critical edge case happens when the only valid solution is removing every element. This occurs when:

x == sum(nums)

In this case, the target remaining subarray sum becomes zero. Since all numbers are positive, the only subarray with sum zero is the empty subarray. The implementation handles this cleanly by returning len(nums) immediately.

A third subtle edge case involves arrays where no valid subarray exists even though x is smaller than the total sum. For example:

nums = [5,6,7,8,9]
x = 4

Here:

target = 31

but no contiguous subarray sums to 31. A naive implementation might accidentally return an incorrect operation count if it does not properly track whether a valid window was ever found. The solution uses max_length = -1 as a sentinel value to detect this case safely.

Another important consideration is that the sliding window technique only works because all numbers are positive. With negative numbers, shrinking the window would not reliably decrease the sum, and the algorithm would fail. The problem constraints guarantee positive integers, which makes the linear sliding window solution correct.