1658. Minimum Operations to Reduce X to Zero #

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’s 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

Problem Summary #

Given an integer array nums and an integer x. In each operation, you should remove the leftmost or rightmost element from the array nums, then subtract that element’s value from x. Note that the array needs to be modified for subsequent operations. If x can be reduced exactly to 0, return the minimum number of operations; otherwise, return -1.

Solution Approach #

• Given an array nums and an integer x, the requirement is to remove some numbers from both ends of the array so that their sum is exactly equal to the integer x, and output the minimum number of operations.
• The requirement is to output the minimum number of operations, that is, the fewest numbers from the two ends of the array, and their sum must be exactly equal to the integer x. Since operating with 2 pointers at the two ends of the array is not very convenient, my idea when solving the problem was to turn it into a circular array, so the pointers on both sides would be within one interval. Use a sliding window to find the smallest window such that the cumulative sum inside the window equals the integer k. This method is feasible, but the code is quite long.
• Is there a more elegant method? Yes. To minimize the lengths at the two ends is equivalent to maximizing the length of the middle segment. This transforms the problem into directly using a sliding window on the array to find the longest contiguous subarray whose cumulative sum equals a fixed value.
• Problems with similar ideas to this one: 209, 1040 (circular array), 325. These 3 problems are highly recommended.

Code #

package leetcode

func minOperations(nums []int, x int) int {
	total := 0
	for _, n := range nums {
		total += n
	}
	target := total - x
	if target < 0 {
		return -1
	}
	if target == 0 {
		return len(nums)
	}
	left, right, sum, res := 0, 0, 0, -1
	for right < len(nums) {
		if sum < target {
			sum += nums[right]
			right++
		}
		for sum >= target {
			if sum == target {
				res = max(res, right-left)
			}
			sum -= nums[left]
			left++
		}
	}
	if res == -1 {
		return -1
	}
	return len(nums) - res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}