Problem Description

You have an integer array nums of length n and a 2D array queries where each queries[i] = [li, ri] represents a range operation.

Each query allows you to:

• Decrement values in the range [li, ri] of nums by at most 1
• You can choose independently for each index whether to decrement it by 0 or 1

Your goal is to convert nums into a Zero Array (all elements equal to 0) using some subset of the given queries.

The problem asks you to find the maximum number of queries you can remove from queries while still being able to convert nums to a zero array using only the remaining queries.

For example, if you have nums = [2, 0, 2] and queries covering different ranges, you need to determine which queries are essential for reducing all values to 0, and which ones can be removed. Each query can reduce values in its range by at most 1, so if nums[i] = 2, you need at least 2 queries that cover index i to reduce it to 0.

Return:

• The maximum number of queries that can be removed if it's possible to achieve a zero array
• -1 if it's impossible to convert nums to a zero array even using all queries

The key constraint is that each query can only reduce values by at most 1, so for any position i with value nums[i], you need at least nums[i] queries covering that position to reduce it to 0.

Intuition

Think about this problem inversely - instead of finding which queries to remove, let's find the minimum number of queries we must use to achieve a zero array. The maximum removals would then be total queries - minimum needed.

For each position i in nums, if nums[i] = k, we need at least k queries that cover position i to reduce it to 0. The challenge is selecting which queries to use efficiently.

Consider a greedy approach: as we traverse the array from left to right, at each position i, we want to ensure we have enough coverage. If we don't have enough coverage yet, which queries should we pick?

The key insight is that we should prefer queries that extend as far to the right as possible. Why? Because a query covering [l, r] with a larger r can help reduce values at more positions to the right, potentially saving us from using additional queries later.

This leads to our strategy:

1. Process positions from left to right
2. At each position, collect all queries that could start covering from this position (those with left endpoint ≤ i)
3. If we need more coverage at position i, greedily select queries that end as late as possible (largest right endpoint)
4. Keep track of when each selected query stops contributing (after its right endpoint)

We can use a max heap to efficiently track and select queries with the largest right endpoints. The difference array helps us maintain the running count of how many queries are currently active at each position.

The queries we never pop from the heap are the ones we "removed" - they weren't necessary for achieving the zero array. If at any position we can't get enough coverage even after using all available queries, it's impossible to achieve a zero array.

Learn more about Greedy, Prefix Sum, Sorting and Heap (Priority Queue) patterns.

Solution Approach

Let's implement the greedy strategy using a difference array and priority queue:

1. Sort queries by left endpoint:

queries.sort()

This ensures we can process queries in order as we traverse the array from left to right.

2. Initialize data structures:

• pq = []: Max heap (using negative values in Python's min heap) to store right endpoints of candidate queries
• d = [0] * (len(nums) + 1): Difference array to track coverage changes
• s = 0: Current coverage count at position i
• j = 0: Pointer to track which queries we've considered

3. Process each position from left to right:

for i, x in enumerate(nums):
    s += d[i]  # Update coverage count with difference array

The difference array tells us how the coverage changes at position i.

4. Add all queries starting at or before position i to the heap:

while j < len(queries) and queries[j][0] <= i:
    heappush(pq, -queries[j][1])  # Store negative for max heap
    j += 1

These are potential queries we could use if needed.

5. Greedily select queries when coverage is insufficient:

while s < x and pq and -pq[0] >= i:
    s += 1                      # Increase coverage
    d[-heappop(pq) + 1] -= 1   # Mark where this query ends

• Check if current coverage s is less than required value x (which is nums[i])
• Ensure the query at heap top still covers position i (-pq[0] >= i)
• Pop the query with the largest right endpoint and apply it
• Increment coverage immediately
• Decrement coverage after the query's right endpoint using the difference array

6. Check feasibility:

if s < x:
    return -1

If we still don't have enough coverage after using all available queries, it's impossible.

7. Return the result:

return len(pq)

The queries remaining in the heap are those we didn't need to use - these are the "removed" queries.

Time Complexity: O(n log n + m log m) where n is the length of nums and m is the number of queries. We sort queries (O(m log m)) and potentially push/pop each query once from the heap (O(m log m)).

Space Complexity: O(n + m) for the difference array and heap.

The brilliance of this approach is that it makes locally optimal choices (picking the longest-reaching query when needed) that lead to a globally optimal solution, maximizing the number of unused queries.

Example Walkthrough

Let's walk through an example with nums = [2, 0, 2] and queries = [[0, 2], [0, 1], [1, 2]].

Initial Setup:

• Sort queries by left endpoint: [[0, 2], [0, 1], [1, 2]] (already sorted)
• Initialize: pq = [], d = [0, 0, 0, 0] (difference array), s = 0 (current coverage), j = 0 (query pointer)

Process position 0 (nums[0] = 2):

1. Update coverage: s = s + d[0] = 0 + 0 = 0
2. Add queries starting at or before position 0:
   • Query [0, 2]: push -2 to heap → pq = [-2]
   • Query [0, 1]: push -1 to heap → pq = [-2, -1]
3. Need coverage of 2, but have 0. Select queries greedily:
   • First selection: Pop -2 (query [0, 2] with right endpoint 2)
     • s = 1, d[3] = -1 (coverage ends after position 2)
   • Second selection: Pop -1 (query [0, 1] with right endpoint 1)
     • s = 2, d[2] = -1 (coverage ends after position 1)
4. Coverage satisfied: s = 2 ≥ nums[0] = 2 ✓

Process position 1 (nums[1] = 0):

1. Update coverage: s = s + d[1] = 2 + 0 = 2
2. Add queries starting at position 1:
   • Query [1, 2]: push -2 to heap → pq = [-2]
3. Need coverage of 0, have 2. No queries needed ✓

Process position 2 (nums[2] = 2):

1. Update coverage: s = s + d[2] = 2 + (-1) = 1 (one query ended after position 1)
2. No new queries to add (all processed)
3. Need coverage of 2, have 1. Select queries greedily:
   • Pop -2 (query [1, 2] with right endpoint 2)
     • s = 2, d[3] += -1 → d[3] = -2
4. Coverage satisfied: s = 2 ≥ nums[2] = 2 ✓

Result:

• Heap is empty: pq = []
• All 3 queries were used, so 0 queries can be removed
• Return: len(pq) = 0

This example shows how the algorithm greedily selects queries with the furthest right endpoints when needed, tracking coverage changes efficiently with the difference array.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m × log m)

The time complexity breaks down as follows:

• Sorting the queries takes O(m × log m) where m is the number of queries
• The main loop iterates through all n elements in nums, taking O(n) time
• Within the main loop:
  • The inner while loop that adds queries to the heap runs at most m times total across all iterations, with each heappush operation taking O(log m)
  • The second inner while loop that pops from the heap also runs at most m times total across all iterations, with each heappop operation taking O(log m)
• Total heap operations: at most m pushes and m pops, each taking O(log m), contributing O(m × log m)
• Overall: O(m × log m) for sorting + O(n) for iteration + O(m × log m) for heap operations = O(n + m × log m)

Space Complexity: O(n + m)

The space complexity consists of:

• The difference array d of size n + 1, taking O(n) space
• The priority queue pq which can contain at most m elements (all queries), taking O(m) space
• Other variables (s, j, i) use O(1) space
• Total: O(n + m)

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

Common Pitfalls

1. Incorrectly Managing Query Availability

A critical pitfall is misunderstanding when queries become available versus when they can actually be used. Many implementations incorrectly assume that a query [l, r] can only be considered when processing index l, missing queries that started earlier but are still valid.

Wrong approach:

# Only considering queries that START at current position
if query[0] == position:
    heappush(heap, -query[1])

Correct approach:

# Consider ALL queries that START at or before current position
while query_index < len(queries) and queries[query_index][0] <= position:
    heappush(available_queries_heap, -queries[query_index][1])
    query_index += 1

2. Not Validating Query Coverage Before Using

Another common mistake is popping queries from the heap without checking if they still cover the current position. Since we're using a max heap based on end positions, a query might have the largest end position but might not actually cover the current index.

Wrong approach:

while current_coverage < required_value and available_queries_heap:
    # Blindly using the query without checking if it covers current position
    current_coverage += 1
    difference_array[-heappop(available_queries_heap) + 1] -= 1

Correct approach:

while current_coverage < required_value and available_queries_heap and -available_queries_heap[0] >= position:
    # Only use query if its end position covers current position
    current_coverage += 1
    difference_array[-heappop(available_queries_heap) + 1] -= 1

3. Difference Array Boundary Issues

A subtle but important pitfall is incorrectly updating the difference array, particularly at the boundaries. The effect of a query covering range [l, r] should end after position r, meaning we need to decrement at position r + 1.

Wrong approach:

# Incorrectly decrementing at position r
difference_array[query_end] -= 1

Correct approach:

# Correctly decrementing at position r + 1
difference_array[query_end_position + 1] -= 1

4. Premature Feasibility Check

Some implementations check if there are enough total queries to cover all positions before processing, but this doesn't account for the range constraints. Just because the sum of all query ranges exceeds the sum of nums doesn't guarantee feasibility.

Wrong approach:

# Check total coverage upfront
total_coverage = sum(r - l + 1 for l, r in queries)
if total_coverage < sum(nums):
    return -1

Correct approach:

# Check feasibility at each position during processing
if current_coverage < required_value:
    return -1

5. Forgetting to Sort Queries

The greedy algorithm relies on processing queries in order of their start positions. Forgetting to sort can lead to missed opportunities to use queries optimally.

Solution: Always sort queries by their left endpoint before processing:

queries.sort()  # Sorts by first element (left endpoint) by default