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

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 + Top Down Dynamic Programming Algorithm + Recursion with Memoization)

We can simulate the process, at each step, we can either remove the element at the right, or the element at the left. Then we recursively find out the answers and return the minimum. If the left pointer crosses over the right pointer, of the sum becomes negative, the current path doesn’t work, we then stop the current path.

We can use a hash table to remember (memoization) the states, which is (L, R, s) where L, R are left and right pointer, and s is the remaining sum. The max number of states is L*R*s, which could be very large because of s could be any sum. So, this solution is not optimial, as it may exceed both time and memory space limits.

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

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        @cache
        def f(L, R, x):
            if x == 0:
                return 0
            if L > R or x < 0:
                return inf
            a = f(L + 1, R, x - nums[L])
            b = f(L, R - 1, x - nums[R])
            ans = min(a, b)
            if ans == inf:
                return ans
            return ans + 1
 
        ans = f(0, len(nums) - 1, x)
        return ans if ans != inf else -1

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        @cache
        def f(L, R, x):
            if x == 0:
                return 0
            if L > R or x < 0:
                return inf
            a = f(L + 1, R, x - nums[L])
            b = f(L, R - 1, x - nums[R])
            ans = min(a, b)
            if ans == inf:
                return ans
            return ans + 1

        ans = f(0, len(nums) - 1, x)
        return ans if ans != inf else -1

We let the recursion function return inf to indicate that no solution exists, so that we can minimize the routes/paths in the search tree.

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) —