1658. Minimum Operations to Reduce X to Zero Medium

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.

Approach

Input: An integer array nums and an integer x

Output: Return the minimum number of operations to reduce x to 0, otherwise return -1.

This problem operates using the Variable-length Sliding Window technique.

We can think about this problem inversely: Transform "taking numbers from both ends to sum to x" into -> "finding the longest contiguous subarray in the middle whose sum is exactly total - x"!

This way we can continuously accumulate values during traversal. When we find the sum is larger than the target value total - x, we remove the leftmost number and continue accumulating towards the right.

Whenever we hit the target sum exactly, we record the maximum length.

Finally, Total length of array - Maximum length will be our answer, representing the minimum number of elements removed to reach the target sum.

Implementation

python

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        # Calculate the total sum of the entire array
        total = sum(nums)
        # Convert into finding the longest subarray whose sum is total - x
        target = total - x

        # If the target is less than 0, it means x is larger than the total sum of the array, impossible
        if target < 0:
            return -1

        # If the target is exactly 0, it means we must remove all elements
        if target == 0:
            return len(nums)

        # Record the length of the longest subarray found (initially -1 means not found)
        maxLen = -1
        # Left pointer of the sliding window
        left = 0
        # Current sum within the window
        currSum = 0

        # Traverse the array, acting as the right boundary of the sliding window
        for right in range(len(nums)):
            currSum += nums[right]  # Add new element

            # If the current window sum is strictly greater than the target, shrink the window (move left pointer)
            while currSum > target and left <= right:
                currSum -= nums[left]
                left += 1

            # If we exactly hit the target sum subarray, update the max length
            if currSum == target:
                maxLen = max(maxLen, right - left + 1)

        # If we found a valid subarray, return the number of deletions required (total length minus retained subarray length)
        return len(nums) - maxLen if maxLen != -1 else -1

javascript

/**
 * @param {number[]} nums
 * @param {number} x
 * @return {number}
 */
var minOperations = function(nums, x) {
    const total = nums.reduce((acc, curr) => acc + curr, 0);

    const target = total - x;

    if (target < 0) return -1;
    if (target == 0) return nums.length;

    let left = 0;
    let maxLen = -1;
    let currSum = 0;

    for (let right = 0; right < nums.length; right++) {
        currSum += nums[right];

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

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

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

Complexity Analysis

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

Links

1658. Minimum Operations to Reduce X to Zero (English)1658. 将 x 减到 0 的最小操作数 (Chinese)