Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each query can decrement any chosen subset of its range. Thus indices do not compete for a shared decrement budget: an index can be reduced to zero exactly when at least nums[i] queries cover it. We only need each position's coverage count.

Approach

Allocate a difference array with one extra position. For every inclusive range [left, right], add one at left and subtract one at right + 1. Prefix-sum this array to recover the number of queries covering each index.

If any value exceeds its coverage count, return false; otherwise return true. Coverage is necessary because a query reduces a selected index by at most one. It is sufficient because each position can independently use the required number of its covering queries and skip the rest, avoiding decrements below zero.

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        n = len(nums)
        arr = [0] * (n + 1)

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

        for i in range(1, n + 1):
            arr[i] += arr[i - 1]

        for i in range(n):
            if nums[i] > arr[i]:
                return False

        return True

Complexity analysis

Let n = nums.length and q = queries.length. Time: O(n + q). Auxiliary space: O(n).