Sliding Window - Minimum Operations to Reduce X to Zero

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.

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.

Input: nums = [5,6,7,8,9], x = 4
Output: -1

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⁹

Solution 1 - Using sliding window technique, find the longest array whose target is 'sum of array - x'

As per the problem statement, we have to find minimum number of elements needed to reduce x to zero, and at a time we can either take left side element or right side element and we have to subtract that element from x. Say if we we have to solve this problem using brute-force approach, we will have to try every number on each side, for the next operation we have to try left side number as well as right side number, since we do not know which of this number will lead us to reduce x to 0, and which one will lead us to minimum number of elements as well. By doing these each and every possibility either left element to consider or right element to consider, the time complexity is going to be 2ⁿ.

So, in this approach, what we are going to do is, find a largest array whose sum is equal to array total sum - x, if we find such array, this means that the remaining elements must be equal to x and those numbers must be minimum number of elements that adds upto x.

Implementation steps:

First, compute the sum of input array elements, call it sum.
Then, compute the remainder = sum -x, and we are goind to find a subarray whose sum is equal to remainder, if there is any.
Next, create two variables left, right that we will use to adjust the window, currentSum to store current window elements sum and longest to keep track of longest subarray found so far when subarray sum is equal to remainder.
Next, run a while loop, while right pointer is within the bounds array length, and do the following:
- Add current element to currentSum.
- Immediately after adding current element to currentSum, check it is greater than the remainder, if it is, then run another while loop and move left pointer and subtract left element value from currentSum, as long as left pointer did not go beyond right pointer (in case if input array has negative values).
- Next, check if currentSum is equal to remainder, it it is, then take the current window size right - left +1 and compare it with longest found so far, and update longest among these two.
- Next, increment right pointer.
Finally, check if longest is greater than 0, that means a subarray is found whose sum is remainder, then return nums.length - longest, that gives minimum number of elements left whose value must be equal to x, and if longest is not greater than 0, then return -1.

package io.cscode.algorithms.slidingwindow; import java.util.stream.IntStream; public class MinOperationsToReduceXToZero { static int minOperations(int[] nums, int x) { int sum = IntStream.of(nums).sum(); if(sum == x) { return nums.length; } int remainder = sum - x; int left =0; int right =0; int currentSum = 0; int longest = 0; while(right < nums.length) { currentSum += nums[right]; while(currentSum >remainder && left<=right) { currentSum -= nums[left]; left++; } if(currentSum == remainder) { longest = Math.max(right - left + 1, longest); } right++; } return longest > 0 ? nums.length - longest : -1; } public static void main(String[] args) { System.out.println(minOperations(new int[]{1,1,4,2,3}, 5)); System.out.println(minOperations(new int[]{5,6,7,8,9}, 4)); System.out.println(minOperations(new int[]{3,2,20,1,1,3}, 10)); System.out.println(minOperations(new int[]{8828,9581,49,9818,9974,9869,9991,10000,10000,10000,9999,9993,9904,8819,1231,6309}, 134365)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time, where n is the length of input array nums.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: