0948MediumArrayPrefix Sum

Can Every Reading Be Cleared

Tracked in this browser only

Trains the technique from

LeetCode 3355Zero Array Transformation I

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Readings are given as nums, and each entry of queries is a pair [l, r].

Working through the queries in order, a query lets you pick any set of positions inside its own range, ends included, and drop each picked reading by one. Picking nothing is allowed, and a reading may never be dropped below zero.

Return true when every reading can be brought down to zero by the time all the queries have been worked through.

Examples

Example 1

Input: nums = [2, 0, 3, 1], queries = [[0, 3], [2, 2], [0, 2], [2, 3]]
Output: true

Position 0 is covered by two queries and reads 2, position 2 is covered by all four and reads 3, and position 3 is covered by two and reads 1, so every reading has enough cover.

Example 2

Input: nums = [1, 1, 1], queries = [[0, 2]]
Output: true

One query covers all three positions, so each can be dropped once, which is exactly what each reading needs.

Example 3

Input: nums = [2], queries = [[0, 0]]
Output: false

The single query can drop the reading only once, leaving it at one.

Constraints

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^5
1 <= queries.length <= 10^5
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] <= nums.length - 1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def is_zero_array(nums: list[int], queries: list[list[int]]) -> bool:

Java

public boolean isZeroArray(int[] nums, int[][] queries)

The intended approach

Time O(n + q) for n readings and q queries.Space O(n) for the coverage counts.

Each query treats its positions independently, and picking a position never costs anything anywhere else, so the positions never compete: a reading can be cleared exactly when the number of queries covering it is at least the reading itself. The order of the queries makes no difference for the same reason. So the whole thing is a coverage count per position, which a difference array gives in one pass: add one where each range opens, take one back just past where it closes, then take a running total. Comparing that count against each reading settles it.

Pythonentry point: is_zero_array

def is_zero_array(nums, queries):
    n = len(nums)
    delta = [0] * (n + 1)
    for l, r in queries:
        delta[l] += 1
        delta[r + 1] -= 1
    running = 0
    for i in range(n):
        running += delta[i]
        if running < nums[i]:
            return False
    return True

The obvious version

For each position, walk the whole list of queries counting those whose range covers it, then compare that count against the reading. Costs the query count per position and builds nothing.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_is_zero_array(nums, queries):
    n = len(nums)
    for i in range(n):
        covers = 0
        for l, r in queries:
            if l <= i <= r:
                covers += 1
        if covers < nums[i]:
            return False
    return True

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in