Minimum Operations To Reduce X To Zero

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

• Using recursion gives memory exceeded, since there are too many stack calls.
• Instead, use a Sliding Window to keep track of which elements must be removed to get x remaining.
• This is easier for a sliding window since in a traditional sliding window, you always remove elements from the left, keeping you with “middle elements remaining” in your window.
• Therefore, by removing those middle elements, if those elements sum up to exactly sum(nums) - x, then you have a candidate of elements that sum up to x.
• And so keep track of the maximum sliding window, which in other words is the maximum number of elements to remove, and return n - that.

Complexity

Runtime

$O(N)$ to apply sliding window, since you do at most N + (N - 1) operations if your left window slid all the way to the right.

Space

$O(1)$

Code

Sliding Window

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        amount_to_remove = sum(nums) - x
        left = 0
        cur_sum = 0
        max_elements_to_remove = -1
        n = len(nums)
        for right in range(n):
            cur_sum += nums[right]
            while left <= right and cur_sum > amount_to_remove:
                cur_sum -= nums[left]
                left += 1
            if cur_sum == amount_to_remove:
                max_elements_to_remove = max(max_elements_to_remove, right - left + 1)
        
        return -1 if max_elements_to_remove == -1 else n - max_elements_to_remove

Memory Limit Exceeded

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        dp = {}
        def rec(l, r, rem, ops):
            if rem < 0:
                return inf
            if rem == 0:
                return ops
            if l > r:
                return inf
 
            if (l, r) in dp:
                return dp[(l, r)]
 
            sr_l = rec(l + 1, r, rem - nums[l], ops + 1)
            sr_r = rec(l, r - 1, rem - nums[r], ops + 1)
            dp[(l, r)] = min(sr_l, sr_r)
            return dp[(l, r)]
        
        res = rec(0, len(nums) - 1, x, 0)
        return -1 if res == inf else res

• Since x is a huge number (23018231), and so the stack trace alone would be huge, meaning you ultimately must use Sliding Window.

Notes

Cards

START Basic Front: Minimum Operations To Reduce X To Zero Back: Return n - “maximum number of operations to have x’ be = sum(nums) - x”

END

---

References

• Minimum Operations To Reduce X To Zero