Zero Array Transformation 3

Problem

You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri].

Each queries[i] represents the following action on nums:

Decrement the value at each index in the range [li, ri] in nums by at most 1.
The amount by which the value is decremented can be chosen independently for each index.

A Zero Array is an array with all its elements equal to 0.

Return the maximum number of elements that can be removed from queries, such that nums can still be converted to a zero array using the remaining queries. If it is not possible to convert nums to a zero array, return -1.

Examples

Example 1:

Input: nums = [2,0,2], queries = [[0,2],[0,2],[1,1]]
Output: 1
Explanation:
After removing `queries[2]`, `nums` can still be converted to a zero array.
  * Using `queries[0]`, decrement `nums[0]` and `nums[2]` by 1 and `nums[1]` by 0.
  * Using `queries[1]`, decrement `nums[0]` and `nums[2]` by 1 and `nums[1]` by 0.

Example 2:

Input: nums = [1,1,1,1], queries = [[1,3],[0,2],[1,3],[1,2]]
Output: 2
Explanation:
We can remove `queries[2]` and `queries[3]`.

Example 3:

Input: nums = [1,2,3,4], queries = [[0,3]]
Output: -1
Explanation:
`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

Method 1 - Using Min heap

Use a min-heap to dynamically track the range end points of active queries that cover each index i in nums.
For each index i, attempt to reduce nums[i] to 0:
- Remove expired ranges and add queries starting at or before i to the heap.
- Use the "shortest" valid range (based on the heap's smallest end index) to incrementally reduce nums[i].
If any index cannot be reduced to 0 using available ranges, return -1.
At the end, the size of the heap gives the number of unused queries.

Code

Java

class Solution {
    public int maxRemoval(int[] nums, int[][] queries) {
        int n = nums.length;
        int qLen = queries.length;

        // Sort queries by their start indices (greedy to process in order of 'li')
        Arrays.sort(queries, (a, b) -> Integer.compare(a[0], b[0]));

        // Min-heap to track the end indices of active queries (negated for min-heap operation)
        PriorityQueue<Integer> activeEnds = new PriorityQueue<>();
        int[] endCount = new int[n + 1]; // Stores decrement counts at indices after the end of ranges

        int currentDecrements = 0; // Tracks active decrements applicable on nums[i]
        int queryIndex = 0;        // To iterate through sorted queries

        // Traverse through every index of nums
        for (int i = 0; i < n; i++) {
            // Remove expired decrements (tied to indices beyond i)
            currentDecrements -= endCount[i];

            // Add new ranges starting at or before i into the heap
            while (queryIndex < qLen && queries[queryIndex][0] <= i) {
                activeEnds.offer(-queries[queryIndex][1]); // Push end index as negative for min-heap
                queryIndex++;
            }

            // Ensure we fulfill nums[i] with available queries
            while (currentDecrements < nums[i]) {
                // If no valid query can cover current index, transformation is impossible
                if (activeEnds.isEmpty() || -activeEnds.peek() < i) {
                    return -1;
                }

                // Use the shortest range available in the heap
                int rangeEnd = -activeEnds.poll();
                endCount[rangeEnd + 1]++; // Deferred decrement subtraction beyond the range
                currentDecrements++;     // Increment active decrements
            }
        }

        // At the end, the heap size represents the number of removable queries
        return activeEnds.size();
    }
}

Python

class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        n = len(nums)
        q_len = len(queries)

        # Sort queries by their start index
        queries.sort(key=lambda x: x[0])

        # Min-heap to store the end indices of active queries
        active_ends = []
        end_count = [0] * (n + 1)  # Decrement offsets for range ends

        current_decrement = 0
        query_idx = 0

        for i in range(n):
            # Remove expired decrements
            current_decrement -= end_count[i]

            # Add all new queries starting at or before index `i` to the heap
            while query_idx < q_len and queries[query_idx][0] <= i:
                heapq.heappush(active_ends, -queries[query_idx][1])
                query_idx += 1

            # Handle nums[i], ensuring it becomes 0
            while current_decrement < nums[i]:
                # If no valid range can cover index `i`, it's impossible
                if not active_ends or -active_ends[0] < i:
                    return -1
                
                # Use the shortest valid range (smallest end index)
                range_end = -heapq.heappop(active_ends)
                end_count[range_end + 1] += 1
                current_decrement += 1

        # The remaining size of the heap indicates the removable queries
        return len(active_ends)

Complexity

⏰ Time complexity: O(q log q + n log q) where is n is number of indices and q is the number of queries.
- Sorting the queries costs O(q log q).
- Each heap operation is O(log q), resulting in a total of O(q log q + n log q) for n indices.
🧺 Space complexity: O(q) for using heap.