Today’s problem

https://leetcode.com/problems/zero-array-transformation-i/

Intuition

This problem means to decrease one in a range (l, r) for each query. To deal with the change of a range, we can consider prefix sum. Note that the question says “Select a subset of indices”, this means that we do not necessarily need to minus 1 for all indices in the range. In this case, because we only care whether the final array is a zero array or not, so instead of testing whether the final array is zero or not, we can test whether the final array is less or equal to zero or not becuase of the subset mentioned in the question.

Approach

For each query, we can add 1 to the difference array at l and add -1 to the difference array at r + 1. Then when we calculate the final answer, we can use the prefix sum to add them up and get the change of the array. Finally, when we want to know whether the final array is zero array or not, we can add the difference array to the original array and test whether each index is less or equal to zero or not to get the answer.

Complexity

• Time complexity:

$O(N + M)$, N is the length of the original array, M is the length of the query.

• Space complexity:

$O(N)$.

Code

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        diff = [0] * (len(nums) + 1)
        for l, r in queries:  
            diff[l] -= 1
            diff[r + 1] += 1
        
        for i in range(len(nums)):
            if i > 0:
                diff[i] += diff[i-1]
            if nums[i] + diff[i] > 0:
                # print(i, nums[i], diff[i])
                return False
        
        return True

For more solutions, please visit My blog