#3362

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Zero Array Transformation III

Zero Array Transformation III requires removing the minimum number of queries to make all elements zero using greedy validation.

array greedy sorting heap priority queue prefix sum

Problem Statement

You are given an integer array nums of length n and a list of queries where each query is a pair [li, ri]. Each query represents an operation that subtracts 1 from every element nums[j] where li <= j <= ri. A Zero Array is an array where all elements are zero.

Determine the minimal number of queries to remove so that after applying the remaining queries in order, nums becomes a zero array. If no such removal exists, return -1.

Examples

Example 1

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

Output: 1

After removing queries[2] , nums can still be converted to a zero array.

Example 2

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

Output: 2

We can remove queries[2] and queries[3] .

Example 3

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

Output: -1

nums cannot be converted to a zero array even after using all the queries.

Constraints

1 <= nums.length <= 105
0 <= nums[i] <= 105
1 <= queries.length <= 105
queries[i].length == 2
0 <= li <= ri < nums.length

Solution Approach

Sort Queries and Track Coverage

Sort the queries by their start index to facilitate a greedy approach. Use a prefix sum array to efficiently accumulate the effects of each query on nums and quickly check the cumulative changes.

Greedy Removal Check

Iterate through nums using the prefix sums to identify the first query that violates the zero array invariant. Remove this query and update the prefix sums, repeating the check to find the minimal removal index.

Validate Zero Array Completion

After removing candidate queries, verify if the remaining queries can transform nums to all zeros. If validation fails for all removals, return -1; otherwise, return the minimal query index found.

Complexity Analysis

Metric	Value
Time	O(n + m \times \log{m})
Space	O(n + m)

Time complexity is O(n + m \times \log{m}) due to sorting m queries and computing prefix sums over n elements. Space complexity is O(n + m) for the prefix sum array and storing sorted queries.

What Interviewers Usually Probe

Pay attention if a candidate sorts queries to apply the greedy choice efficiently.
Watch for correct prefix sum usage to track cumulative operations on nums.
Check if the candidate validates the zero array invariant at each step.

Common Pitfalls or Variants

Common pitfalls

Failing to sort queries before applying the greedy removal can lead to incorrect minimal removal.
Neglecting prefix sum updates after removing a query may break invariant checks.
Returning a valid index without fully confirming nums becomes zero after all remaining queries.

Follow-up variants

Allow queries to both increment and decrement, requiring signed prefix sums.
Optimize for very large n with sparse queries using segment trees instead of full prefix sums.
Find the maximal number of removable queries while still achieving a zero array.

FAQ

What is the primary strategy for solving Zero Array Transformation III?

The main strategy is greedy choice plus invariant validation using sorted queries and prefix sums to track cumulative changes.

Can all arrays always be converted to zero arrays?

No, some nums arrays cannot reach all zeros even after applying all queries; in such cases, the solution returns -1.

Why is sorting queries important in this problem?

Sorting ensures that greedy removal checks respect the left-to-right order, preventing premature violation of the zero array invariant.

How does the prefix sum optimize the solution?

Prefix sums allow O(1) range updates for queries and fast cumulative effect computation, avoiding repeated iteration over nums.

What common mistakes should I avoid in Zero Array Transformation III?

Avoid failing to validate the zero array after removals, neglecting prefix sum updates, and misordering queries during the greedy process.

terminal

Solution

Solution 1: Greedy + Difference Array + Priority Queue

We want to "remove" as many interval queries as possible, while ensuring that for each position $i$, the number of selected queries covering it, $s(i)$, is at least the original array value $\textit{nums}[i]$, so that the value at that position can be reduced to 0 or below. If for some position $i$ we cannot satisfy $s(i) \ge \textit{nums}[i]$, it means that no matter how many more queries we select, it is impossible to make that position zero, so we return $-1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        queries.sort()
        pq = []
        d = [0] * (len(nums) + 1)
        s = j = 0
        for i, x in enumerate(nums):
            s += d[i]
            while j < len(queries) and queries[j][0] <= i:
                heappush(pq, -queries[j][1])
                j += 1
            while s < x and pq and -pq[0] >= i:
                s += 1
                d[-heappop(pq) + 1] -= 1
            if s < x:
                return -1
        return len(pq)

Continue Practicing

#2406 divide intervals into minimum number of groups #3413 maximum coins from k consecutive bags #3462 maximum sum with at most k elements