Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Retained queries only need to supply enough coverage at every index. When the current index is undercovered, choose an available query ending as far right as possible. It supplies the same needed coverage now and remains useful for at least as long as any shorter alternative.

Approach

Process indices from left to right and add newly starting queries' endpoints to an ordered available collection. Python sorts queries in reverse and pops from the end; JavaScript sorts forward and advances an index. A second ordered collection, current, holds end positions of selected queries still covering this index. Remove selected intervals that have expired.

While current coverage is less than nums[i], take the farthest-ending available query. If none reaches i, return -1; otherwise select it and repeat. Earlier positions already have sufficient coverage from previously selected queries. Replacing a shorter additional choice with this farther-reaching interval therefore preserves that coverage and can only help later positions.

Python keeps expired unused queries in available and returns its final size, the number never selected. JavaScript removes expired unused queries during the scan, so it instead counts all selections and subtracts that count from the original number of queries. Both return the maximum number removable.

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

        available = SortedList()
        current = SortedList()

        for i in range(n):
            while queries and queries[-1][0] == i:
                available.add(queries.pop()[1])
            while current and current[0] < i:
                current.pop(0)
            while len(current) < nums[i]:
                if not available or available[-1] < i: return -1
                current.add(available.pop())
            if len(current) < nums[i]: return -1
        
        return len(available)

Complexity analysis

Let n = nums.length and q = queries.length. JavaScript's AVL multisets and sorting give O((n + q) log(q + 1)) worst-case time. Python uses block-based SortedList containers, whose updates are approximately logarithmic in practice, not strict worst-case logarithmic; O(n + q log(q + 1)) is a practical estimate and O(n + q^2) a conservative bound allowing linear-time block updates. Each query is inserted, selected and expired at most once in each relevant collection. Both versions use O(q) auxiliary space including sorting.