Problem Statement in English

You’re given an array of integers nums and a 2D array queries where queries[i] = [l, r]. For each query, you can perform the following operation:

  • For each index j in the range l <= j <= r, you can decrease nums[j] by 1.

Return true if it’s possible to make all elements of nums equal to 0 after performing the above operation for all queries, and false otherwise.

Approach

We just need to accumulate the increases and decreases for each index and check if the final value of each index is less than or equal to 0.

To do this we can use a hashmap to store the increases and decreases for each index. For each query, we can increase the value at index l by 1 and decrease the value at index r + 1 by 1. This way we can accumulate the changes for each index.

After processing all queries, we can iterate through the nums array and check if the final value of each index is less than or equal to 0.

If we find any index where the final value is greater than 0, we can return false. If we successfully check all indices, we can return true.

And we’re done!

Solution in Python


class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        hm = defaultdict(int)

        for l, r in queries:
            hm[l] += 1
            hm[r + 1] -= 1

        curr = 0

        for i in range(len(nums)):
            curr += hm[i]

            if nums[i] - curr > 0:
                return False

        return True

Complexity

  • Time: $O(n + m)$
    Where $n$ is the length of nums and $m$ is the number of queries.

  • Space: $O(m)$
    Where $m$ is the number of queries.

And we are done.