Zero Array Transformation III - Solution & Explanation

The goal is to reduce the nums array to all zeros using the fewest possible queries. To efficiently adjust multiple ranges in the nums array, we can employ a 'difference array' to record the increment/decrement at particular indices. This allows constant-time updates over a subrange.

Once the necessary decrements for each range are calculated, test different combinations of queries to find the maximal number of query removals that still result in nums becoming all zeros.

This code applies the difference array technique. It processes the queries to adjust the nums array, then tests all subarrays of the query sequences by removing one query at a time. If zero array can be achieved by skipped queries, it outputs the number of skippable queries. The approach is greedy – trying minimal number of changes until zero array is possible.

This approach involves treating queries in a greedily prioritized manner. Using a priority queue to always select and process a query that maximizes the zero effect over the largest overlapping range just after it processes the overlapping range, thus allowing maximum flexibility in decrements.

The C++ solution employs a min-heap to greedily select the smallest possible range query to remove, ensuring efficiency by always considering the next largest decrement range effectively. This ensures that minimal queries are used to zero the nums array, while making sure a removal is beneficial.

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 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 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.

To achieve this, we traverse the queries in order of their left endpoints and maintain:

1. Difference array d: Used to record where the currently applied queries take effect—when we "apply" a query on the interval [l, r], we immediately do d[l] += 1 and d[r+1] -= 1. This way, when traversing to index i, the prefix sum tells us how many queries cover i.
2. Max heap pq: Stores the right endpoints of the current "candidate" interval queries (store as negative numbers to simulate a max heap in Python's min heap). Why choose the "latest ending" interval? Because it can cover farther positions. Our greedy strategy is: at each i, only pick the longest interval from the heap when necessary to increase coverage, so that more intervals are available for subsequent positions.

The specific steps are as follows:

1. Sort queries by the left endpoint l in ascending order;
2. Initialize the difference array d with length n+1 (to handle the decrement at r+1), and set the current coverage count s=0, heap pointer j=0;

3. For i=0 to n-1:

   • First, add d[i] to s to update the current coverage count;
   • Push all queries [l, r] with left endpoint \le i into the max heap pq (store -r), and advance j;

   • While the current coverage s is less than the required value nums[i], and the heap is not empty, and the top interval in the heap still covers i (i.e., -pq[0] \ge i):

     1. Pop the top of the heap (the longest interval), which is equivalent to "applying" this query;
     2. Increment s by 1 and do d[r+1] -= 1 (so that after passing r, the coverage count automatically decreases);

   • Repeat the above steps until s \ge nums[i] or no more intervals can be selected;

   • If at this point s < nums[i], it means it is impossible to make position i zero, so return -1.

4. After traversing all positions, the intervals remaining in the heap are those that were not popped, i.e., the queries that are truly retained (not used for the "zeroing" task). The heap size is the answer.

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