Problem Description

You have an integer array nums of length n and a 2D array queries where each query is represented as queries[i] = [li, ri].

For each query, you need to:

1. Select any subset of indices within the range [li, ri] in the array nums (you can choose any indices between position li and ri, inclusive)
2. Decrement the values at your selected indices by 1

A Zero Array is defined as an array where all elements equal 0.

Your task is to determine if it's possible to transform nums into a Zero Array by processing all the queries sequentially. Return true if it's possible, otherwise return false.

The key insight is that for each query [li, ri], you can optimally choose which indices to decrement within that range. You want to strategically select indices to maximize the reduction where needed. Each query gives you the opportunity to reduce values by 1 at any positions within its specified range.

For example, if nums = [1, 0, 2] and you have a query [0, 2], you could choose to decrement indices 0 and 2 (skipping index 1 since it's already 0), resulting in [0, 0, 1].

The solution uses a difference array technique to track the maximum number of times each position can be decremented across all queries. By accumulating these potential decrements and comparing with the original values in nums, we can determine if enough decrements are available at each position to reduce it to zero.

Intuition

The key observation is that for each query [l, r], we can choose to decrement any subset of indices within that range. This means we have complete flexibility in how to apply each query's decrements.

Think about it from each position's perspective: if position i is covered by multiple queries, we can potentially decrement it multiple times (once per covering query). For example, if position 2 is covered by queries [0, 3], [2, 5], and [1, 2], then we can decrement position 2 up to 3 times total.

This leads to a crucial insight: for each position i in nums, we need to check if the number of queries that cover position i is at least nums[i]. If yes, we can reduce nums[i] to zero by strategically using the available decrements from covering queries.

But how do we efficiently count how many queries cover each position? We could iterate through all queries for each position, but that would be inefficient.

This is where the difference array technique comes in. Instead of marking each position individually for every query, we can use a clever trick:

• When a query [l, r] starts at position l, we mark +1 at position l
• When it ends at position r, we mark -1 at position r + 1

By doing a prefix sum scan of these marks, we automatically get the count of active queries at each position. The prefix sum at position i tells us exactly how many queries cover that position.

Finally, we compare: if at any position i, the value nums[i] is greater than the number of available decrements (the prefix sum), then it's impossible to reduce that position to zero, and we return false. Otherwise, we have enough decrements everywhere, so we return true.

Learn more about Prefix Sum patterns.

Solution Approach

We implement the solution using a difference array technique to efficiently track the coverage of queries.

Step 1: Initialize the Difference Array

• Create an array d of length n + 1 (one extra position for boundary handling)
• Initialize all values to 0

Step 2: Process Each Query For each query [l, r] in queries:

• Add 1 to d[l] (marking the start of the query range)
• Subtract 1 from d[r + 1] (marking the end of the query range)

This difference array setup allows us to later compute how many queries cover each position using a prefix sum.

Step 3: Check if Transformation is Possible

• Initialize a running sum s = 0
• Iterate through each position i from 0 to n - 1:
  • Add d[i] to the running sum: s += d[i]
  • The value of s now represents the number of queries that cover position i
  • If nums[i] > s, it means we don't have enough decrements available at position i to reduce it to zero, so return False

Step 4: Return Result

• If we successfully check all positions without finding any impossible cases, return True

Why This Works: The difference array with prefix sum gives us the exact count of how many times each position can be decremented. When we mark +1 at the start of a range and -1 at the end+1, the prefix sum automatically maintains the count of "active" query ranges at each position.

For example, if queries are [[0, 2], [1, 3]]:

• After processing: d = [1, 1, 0, -1, -1, ...]
• Prefix sums give: [1, 2, 2, 1, 0, ...]
• This correctly shows position 0 is covered by 1 query, positions 1-2 are covered by 2 queries, position 3 by 1 query, etc.

The time complexity is O(n + m) where n is the length of nums and m is the number of queries, and space complexity is O(n).

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Example: nums = [3, 2, 1, 2], queries = [[0, 2], [1, 3], [2, 3]]

Step 1: Initialize the difference array

• Create array d of length 5 (n + 1): d = [0, 0, 0, 0, 0]

Step 2: Process each query

Query 1: [0, 2]

• Mark start: d[0] += 1 → d = [1, 0, 0, 0, 0]
• Mark end: d[2+1] -= 1 → d = [1, 0, 0, -1, 0]

Query 2: [1, 3]

• Mark start: d[1] += 1 → d = [1, 1, 0, -1, 0]
• Mark end: d[3+1] -= 1 → d = [1, 1, 0, -1, -1]

Query 3: [2, 3]

• Mark start: d[2] += 1 → d = [1, 1, 1, -1, -1]
• Mark end: d[3+1] -= 1 → d = [1, 1, 1, -1, -2]

Step 3: Check if transformation is possible

Now we iterate through positions 0 to 3, maintaining a running sum to count available decrements:

• Position 0: s = 0 + d[0] = 0 + 1 = 1
  • nums[0] = 3, available decrements = 1
  • Since 3 > 1, we cannot reduce position 0 to zero
  • Return False

The algorithm would return False because position 0 needs 3 decrements but only 1 query covers it.

Alternative example where it works: nums = [1, 2, 2, 1], same queries

Following the same process, we get d = [1, 1, 1, -1, -2]

Checking each position:

• Position 0: s = 1, nums[0] = 1 → 1 ≤ 1 ✓
• Position 1: s = 1 + 1 = 2, nums[1] = 2 → 2 ≤ 2 ✓
• Position 2: s = 2 + 1 = 3, nums[2] = 2 → 2 ≤ 3 ✓
• Position 3: s = 3 + (-1) = 2, nums[3] = 1 → 1 ≤ 2 ✓

All positions can be reduced to zero, so return True.

The prefix sum at each position tells us the maximum number of times we can decrement that position across all queries. As long as this maximum is at least as large as the original value, we can strategically choose when to apply decrements to reach zero.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m)

The algorithm consists of two main parts:

1. Processing all queries to build the difference array d, which iterates through m queries with constant time operations for each query: O(m)
2. Iterating through the array nums and the difference array d simultaneously using zip to check if each element can be reduced to zero: O(n)

Therefore, the total time complexity is O(n + m), where n is the length of the array nums and m is the number of queries.

Space Complexity: O(n)

The algorithm creates a difference array d of size len(nums) + 1, which requires O(n) extra space. The variable s for tracking the cumulative sum uses constant space O(1). Thus, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Difference Array Size

A frequent mistake is creating the difference array with size n instead of n+1. This leads to an index out of bounds error when trying to mark the end of a query range at difference_array[right + 1].

Incorrect:

difference_array = [0] * len(nums)  # Wrong size!
for left, right in queries:
    difference_array[left] += 1
    difference_array[right + 1] -= 1  # IndexError when right == n-1

Correct:

difference_array = [0] * (len(nums) + 1)  # Extra element for boundary

2. Misunderstanding Query Semantics

Developers might incorrectly assume they must decrement ALL indices in the range [l, r] for each query, rather than understanding they can choose ANY subset. This leads to overly pessimistic solutions that return False when the answer should be True.

Incorrect Interpretation:

# Wrong: Assuming we must decrement everything in range
for left, right in queries:
    for i in range(left, right + 1):
        nums[i] -= 1  # This forces all indices to be decremented

Correct Understanding: The difference array tracks the MAXIMUM possible decrements available at each position, allowing optimal selection.

3. Direct Array Modification

Modifying the nums array directly while processing queries destroys the original values needed for comparison. This makes it impossible to correctly determine if transformation is possible.

Incorrect:

for left, right in queries:
    for i in range(left, right + 1):
        if nums[i] > 0:
            nums[i] -= 1  # Modifying original array
# Can't properly check anymore since nums is changed

Correct: Keep nums unchanged and track available decrements separately using the difference array technique.

4. Forgetting to Accumulate the Difference Array

Simply checking difference_array[i] >= nums[i] without accumulating the prefix sum will give incorrect results, as the difference array stores deltas, not the actual coverage count.

Incorrect:

for i in range(len(nums)):
    if nums[i] > difference_array[i]:  # Wrong! Not accumulated
        return False

Correct:

cumulative_reduction = 0
for i in range(len(nums)):
    cumulative_reduction += difference_array[i]  # Accumulate first
    if nums[i] > cumulative_reduction:
        return False