Leetcode: 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'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.

 array의 양끝에서 숫자를 pop할 수 있고, 이 숫자를 x에서 차감할 때 x == 0이 될때까지 pop해야 하는 숫자의 최소 갯수를 구하는 문제이다. 양끝에서 숫자를 뽑는 문제이지만, 바꾸어 생각하면 nums에서 그 합이 sum(nums)-x 인 subarray를 구하는 문제가 된다.

 

첫 번째 방법으로, accumulated sum을 이용할 수 있다. 

from itertools import accumulate
from typing import List

# Time Complexity: O(N)
# Space Complexity: O(N)
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        cum_sum = list(accumulate(nums))
        d = {s: i for i, s in enumerate(cum_sum)}

        target = cum_sum[-1] - x
        if target < 0: return -1

        answer = len(nums)-1-d[target] if target in d else float("inf")
        for num in d:
            if num + target in d:
                answer = min(answer, d[num] + len(nums) - d[num + target])

        return answer if answer != float("inf") else -1

nums array의 accumulated sum을 구하고, 이를 dictionary에 저장한다. 

nums[i]~nums[j]까지의 subarray의 sum은, nums[j]까지의 accumulated sum - nums[i-1]까지의 accumulated sum이 된다. 이를 바꾸어 이야기하면, nums[i]까지의 accumulated sum이 X라고 할 때 합이 target인 subarray가 존재하려면, accumulated sum이 X+target인 인덱스가 존재해야 한다. 이처럼 각각의 accumulated sum에 대해 계산을 하면, Time Complexity는 O(N), Space Complexity는 O(N)이 된다. 

 

accumulated sum을 구하지 않고 추가적인 메모리 없이 문제를 풀려면, two pointer approach를 사용한다.

# Time Complexity: O(N)
# Space Complexity: O(1)
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        target = sum(nums) - x
        if target < 0: return -1

        l, answer = 0, float("inf")
        for r in range(len(nums)):
            target -= nums[r]
            while target < 0:
                target += nums[l]
                l += 1

            if target == 0: answer = min(answer, l + len(nums) - 1 - r)

        return answer if answer != float("inf") else -1

left, right 두 개의 포인터를 움직이며 left~right 사이의 합이 sum(nums)-x인 경우 answer를 업데이트한다. target은 목표하는 합까지 남은 숫자이며, 이 값이 0이 될 경우 left~right 의 값이 sum(nums)-x이 된다. target이 0보다 작은 경우는 해당 array에서 숫자가 빠져야 하므로, left pointer 값을 움직인다. 이렇게 Two Pointer approach를 이용하면 O(N) Time Complexity, O(1) Space Complexity로 특정 합을 가지는 subarray의 sum을 구할 수 있다. 

 

 

링크: leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/

Minimum Operations to Reduce X to Zero - LeetCode