Show problems as
Classic problem #3355MediumArrayPrefix Sum

Zero Array Transformation I

Real-world version: Can Every Reading Be Cleared
Tracked in this browser only
Read Zero Array Transformation I on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def is_zero_array(nums: list[int], queries: list[list[int]]) -> bool:
Java
public boolean isZeroArray(int[] nums, int[][] queries)

More on the same topics