LeetCode 3362 - Zero Array Transformation III

LeetCode Problem 3362

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy, Sorting, Heap (Priority Queue), Prefix Sum

Solution

Problem Understanding

We are given an integer array nums and a list of interval queries. Each query [l, r] allows us to reduce every element inside that range by at most 1. The important detail is that the decrement is optional and independent for every index in the range.

This means a single query can contribute at most one unit of reduction to each covered index. If an index i is covered by k chosen queries, then we can reduce nums[i] by at most k.

The goal is not to minimize the number of queries we use directly. Instead, we want to remove as many queries as possible while still being able to transform the entire array into all zeroes using the remaining queries.

Another way to think about the problem is this:

• Every index i needs exactly nums[i] units of coverage.
• Each query contributes 1 unit of possible coverage to every position in its interval.
• We want to keep the minimum number of queries that still satisfy all coverage requirements.
• The answer is:

total_queries - minimum_queries_needed

If even using all queries cannot provide enough coverage for some index, the answer is -1.

The constraints are large:

• n <= 100000
• queries.length <= 100000

This immediately rules out expensive interval simulation approaches such as repeatedly updating ranges or trying subsets of queries.

Several edge cases are important:

• Some nums[i] may already be 0, meaning that index does not require any coverage.
• Some indices may not be covered by enough queries at all, making the answer -1.
• Queries can overlap heavily.
• Multiple queries may start or end at the same position.
• A greedy choice that looks locally optimal can become globally inefficient if we choose short intervals too early.

The challenge is therefore to select the smallest set of intervals that collectively provide enough coverage for every position.

Approaches

Brute Force Approach

A brute force solution would try all subsets of queries and check whether the remaining queries can still reduce the array to zero.

For each subset:

1. Count how many chosen queries cover every index.
2. Verify whether coverage at index i is at least nums[i].
3. Track the subset using the fewest queries.

This works because the condition for feasibility is simply coverage count per index.

However, the number of subsets is 2^m, where m is the number of queries. With up to 100000 queries, this is completely infeasible.

Even a less extreme brute force approach that greedily tests removals one by one would still require repeatedly recomputing interval coverage, leading to quadratic behavior.

Key Insight

The problem can be reframed as a coverage optimization problem.

At every index i, we need at least nums[i] active intervals covering that position.

Suppose we process indices from left to right. When we arrive at position i, we know:

• which chosen intervals are still active,
• how much coverage we already have,
• and whether we need additional intervals.

If more intervals are needed, the optimal greedy strategy is:

Choose the interval that extends farthest to the right.

Why?

Because longer intervals continue helping future positions. A short interval may satisfy the current index but expire quickly, forcing us to select additional intervals later.

This is a classic greedy interval covering principle.

To implement this efficiently:

• Sort queries by starting position.
• Use a max heap to store candidate intervals by ending position.
• Use another heap to track active chosen intervals.
• Use a difference-array style sweep to efficiently maintain current coverage.

This gives an O(m log m) solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^m * n)	O(n)	Tries every subset of queries
Optimal Greedy + Heap	O((n + m) log m)	O(m)	Greedy interval selection with priority queues

Algorithm Walkthrough

1. Sort all queries by their starting index.

This allows us to process intervals incrementally as we sweep from left to right across the array. 2. Maintain a max heap of candidate intervals.

For every position i, add all queries whose left endpoint is <= i.

We want to choose intervals with the largest right endpoint first, so we store negative right endpoints in Python's min heap to simulate a max heap. 3. Maintain the current active coverage count.

When we select a query, it contributes coverage from its start through its end.

Instead of updating every index in that range directly, we use a difference-array technique:

• Increment current coverage immediately.
• Schedule a future decrement at r + 1.

4. Remove expired active intervals.

Before processing position i, subtract any scheduled coverage removals. 5. Check whether current coverage satisfies nums[i].

If current coverage is already large enough, move on.

Otherwise, repeatedly select additional intervals from the candidate heap. 6. When selecting a new interval:

• Choose the interval with the farthest right endpoint.

• If its right endpoint is before i, it cannot help anymore, so discard it.

• Otherwise:

• increase active coverage,

• schedule its expiration,

• increment the count of used queries.

7. If at some point we still cannot satisfy nums[i], return -1.

This means even all available intervals are insufficient. 8. After processing all positions:

• Let used be the minimum number of required queries.
• Return:

total_queries - used

Why it works

The greedy choice is optimal because whenever additional coverage is required at position i, choosing the interval with the farthest right endpoint maximizes future usefulness.

Any shorter interval could be replaced with the farther-reaching interval without hurting feasibility, while potentially helping future indices more. Therefore, the greedy strategy never uses more intervals than necessary.

The sweep-line structure guarantees that coverage counts are always accurate for the current position.

Python Solution

from typing import List
import heapq

class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        queries.sort()

        n = len(nums)
        m = len(queries)

        # Max heap using negative right endpoints
        available = []

        # Difference array for coverage expiration
        diff = [0] * (n + 1)

        current_coverage = 0
        used_queries = 0
        query_index = 0

        for i in range(n):
            current_coverage += diff[i]

            # Add all queries starting at or before i
            while query_index < m and queries[query_index][0] <= i:
                l, r = queries[query_index]
                heapq.heappush(available, -r)
                query_index += 1

            # Add more intervals if coverage is insufficient
            while current_coverage < nums[i]:
                # Remove unusable intervals
                while available and -available[0] < i:
                    heapq.heappop(available)

                if not available:
                    return -1

                farthest_right = -heapq.heappop(available)

                used_queries += 1
                current_coverage += 1

                if farthest_right + 1 < len(diff):
                    diff[farthest_right + 1] -= 1

        return m - used_queries

The implementation begins by sorting the queries by starting position. This lets us progressively add intervals into the heap as we sweep across the array.

The available heap stores candidate intervals that can currently be chosen. Since Python's heapq is a min heap, we push negative right endpoints so that intervals with the farthest reach are chosen first.

The diff array implements lazy range updates. Instead of explicitly marking every covered position, we:

• immediately increase coverage when selecting an interval,
• then schedule a decrement after the interval ends.

At each index:

• expired effects are applied,
• newly available intervals are inserted,
• and additional intervals are greedily selected until the required coverage is met.

If no valid interval remains when additional coverage is required, the transformation is impossible and we return -1.

Finally, we subtract the number of used intervals from the total number of queries to determine how many can be removed.

Go Solution

package main

import (
	"container/heap"
	"sort"
)

type MaxHeap []int

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	value := old[n-1]
	*h = old[:n-1]
	return value
}

func maxRemoval(nums []int, queries [][]int) int {
	sort.Slice(queries, func(i, j int) bool {
		if queries[i][0] == queries[j][0] {
			return queries[i][1] < queries[j][1]
		}
		return queries[i][0] < queries[j][0]
	})

	n := len(nums)
	m := len(queries)

	diff := make([]int, n+1)

	currentCoverage := 0
	usedQueries := 0
	queryIndex := 0

	available := &MaxHeap{}
	heap.Init(available)

	for i := 0; i < n; i++ {
		currentCoverage += diff[i]

		for queryIndex < m && queries[queryIndex][0] <= i {
			r := queries[queryIndex][1]
			heap.Push(available, r)
			queryIndex++
		}

		for currentCoverage < nums[i] {
			for available.Len() > 0 && (*available)[0] < i {
				heap.Pop(available)
			}

			if available.Len() == 0 {
				return -1
			}

			farthestRight := heap.Pop(available).(int)

			usedQueries++
			currentCoverage++

			if farthestRight+1 < len(diff) {
				diff[farthestRight+1]--
			}
		}
	}

	return m - usedQueries
}

The Go solution follows the exact same greedy strategy as the Python version.

Since Go does not provide a built-in max heap, we implement one using the container/heap package and reverse the comparison in Less().

The difference array behaves identically to the Python implementation. Go slices are naturally dynamic enough for this problem size, and integer overflow is not a concern because all counts stay within 100000.

Worked Examples

Example 1

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

After sorting:

[[0,2],[0,2],[1,1]]

i	nums[i]	Available Heap	Current Coverage	Action
0	2	[2,2]	0	Need 2 intervals
0	2	[2]	1	Pick interval [0,2]
0	2	[]	2	Pick interval [0,2]
1	0	[1]	2	Already enough
2	2	[1]	2	Already enough

Used queries = 2

Total queries = 3

Answer:

3 - 2 = 1

Example 2

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

Sorted:

[[0,2],[1,2],[1,3],[1,3]]

i	nums[i]	Heap	Coverage	Action
0	1	[2]	0	Pick [0,2]
1	1	[3,3,2]	1	Enough
2	1	[3,3,2]	1	Enough
3	1	[3,3]	0	Pick [1,3]

Used queries = 2

Total queries = 4

Answer:

4 - 2 = 2

Example 3

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

i	nums[i]	Coverage Possible
0	1	1
1	2	1

At index 1, we need coverage 2 but only one interval exists.

Therefore the answer is:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + m) log m)	Each query is pushed and popped from the heap at most once
Space	O(m)	Heap and auxiliary structures store up to all queries

The dominant cost comes from heap operations. Since every query enters and leaves the heap at most one time, the total number of heap operations is linear in the number of queries, each costing O(log m).

The difference-array sweep itself is linear.

Test Cases

from typing import List

class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        import heapq

        queries.sort()

        n = len(nums)
        m = len(queries)

        available = []
        diff = [0] * (n + 1)

        current_coverage = 0
        used_queries = 0
        query_index = 0

        for i in range(n):
            current_coverage += diff[i]

            while query_index < m and queries[query_index][0] <= i:
                heapq.heappush(available, -queries[query_index][1])
                query_index += 1

            while current_coverage < nums[i]:
                while available and -available[0] < i:
                    heapq.heappop(available)

                if not available:
                    return -1

                r = -heapq.heappop(available)

                used_queries += 1
                current_coverage += 1

                if r + 1 < len(diff):
                    diff[r + 1] -= 1

        return m - used_queries

sol = Solution()

assert sol.maxRemoval([2,0,2], [[0,2],[0,2],[1,1]]) == 1  # example 1
assert sol.maxRemoval([1,1,1,1], [[1,3],[0,2],[1,3],[1,2]]) == 2  # example 2
assert sol.maxRemoval([1,2,3,4], [[0,3]]) == -1  # example 3

assert sol.maxRemoval([0,0,0], [[0,2]]) == 1  # all nums already zero
assert sol.maxRemoval([1], [[0,0]]) == 0  # single exact interval
assert sol.maxRemoval([2], [[0,0]]) == -1  # insufficient coverage
assert sol.maxRemoval([1,1], [[0,0],[1,1]]) == 0  # both intervals required
assert sol.maxRemoval([1,1], [[0,1],[0,1],[0,1]]) == 2  # only one interval needed
assert sol.maxRemoval([3,3,3], [[0,2],[0,2],[0,2]]) == 0  # all queries required
assert sol.maxRemoval([1,0,1], [[0,0],[2,2],[0,2]]) == 1  # greedy should prefer longer interval
assert sol.maxRemoval([2,1,2], [[0,2],[0,1],[1,2],[0,2]]) == 1  # overlapping intervals

Test Summary

Test	Why
[2,0,2]	Verifies example 1
[1,1,1,1]	Verifies example 2
[1,2,3,4]	Verifies impossible case
All zeros	Ensures unnecessary queries are removable
Single element exact coverage	Smallest valid input
Single element insufficient coverage	Detects impossible coverage
Two disjoint intervals	Ensures both are required
Multiple redundant intervals	Tests maximum removals
Long interval preferred	Validates greedy correctness
Heavy overlap	Tests heap and coverage handling

Edge Cases

One important edge case occurs when all elements in nums are already zero. In this situation, no queries are needed at all, so every query can be removed. A buggy implementation might still select intervals unnecessarily. The greedy coverage check prevents this because it only selects intervals when current coverage is below the required value.

Another critical edge case is insufficient total coverage. For example:

nums = [2]
queries = [[0,0]]

Even using every query, index 0 can only be decremented once. The implementation correctly detects this when the heap becomes empty before satisfying the required coverage.

A third subtle edge case involves overlapping intervals with different lengths. Suppose both short and long intervals can satisfy the current position. Choosing the short interval greedily may force additional selections later. The algorithm avoids this by always choosing the interval with the farthest right endpoint, guaranteeing maximal future usefulness.

Finally, expired intervals must be removed carefully. Intervals whose right endpoint is smaller than the current index can no longer contribute coverage. If these stale intervals remain in the heap, the algorithm may incorrectly assume valid coverage still exists. The implementation explicitly removes expired intervals before selecting new ones.