Teaching Kids Programming – Minimum Operations to Reduce X to Zero (Two Pointer Sliding Window Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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^5
1 <= nums[i] <= 10^4
1 <= x <= 10^9

Minimum Operations to Reduce X to Zero (Two Pointer Sliding Window Algorithm)

Last lesson, we talked about using the Recursion with Memoization aka the Top Down Dynamic Programming Algorithm to Solve this Problem using the Two Pointer Idea: Teaching Kids Programming – Minimum Operations to Reduce X to Zero (Two Pointer + Top Down Dynamic Programming Algorithm + Recursion with Memoization).

We can tackle the opposite problem easily, which is to find out the longest subarray with the given sum (total sum minus the X). Thus, we can apply the Sliding Window (Two Pointer) algorithm to solve this problem. And once, we have the longest sub array, the number of operation (answer) is the total length minus the length.

We keep accumulate the numbers on the right and when the sum of the current window exceeds the target, we need to shrink the window by moving the left pointer. Two pointer algorithms runs at O(N) time as both pointers (left and right) move one direction only and it takes N iterations for the right pointer to reach beyond the right boundary.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        n = len(nums)
        total = sum(nums)
        T = total - x
        L = 0
        R = 0
        ans = -1
        s = 0
        while R < n:
            s += nums[R]
            while s > T and L <= R:
                s -= nums[L]
                L += 1
            if s == T:
                ans = max(ans, R - L + 1)
            R += 1
        return n - ans if ans != -1 else -1

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        n = len(nums)
        total = sum(nums)
        T = total - x
        L = 0
        R = 0
        ans = -1
        s = 0
        while R < n:
            s += nums[R]
            while s > T and L <= R:
                s -= nums[L]
                L += 1
            if s == T:
                ans = max(ans, R - L + 1)
            R += 1
        return n - ans if ans != -1 else -1

When the X equals to the sum of all the numbers, meaning that we need to remove all the numbers, in this case, the subarray sum is zero, and the window size will be kept to zero at each iteration. Alternatively, we can simply check if the X is equal to the total sum, then return N immediately.

On another hand, if the X equals zero, we should return zero as no operations is needed. The target of the subarray sum is the total sum, and the right pointer will take every number in the array, the window size would be N.

Algorithms to Minimum Operations to Reduce X to Zero

• Teaching Kids Programming - Minimum Operations to Reduce X to Zero (Two Pointer Sliding Window Algorithm)
• Teaching Kids Programming - Minimum Operations to Reduce X to Zero (Two Pointer + Top Down Dynamic Programming Algorithm + Recursion with Memoization)

–EOF (The Ultimate Computing & Technology Blog) —