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

maxRemoval.js

/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number}
 */
var maxRemoval = function(nums, queries) {
    const n = nums.length;
    const m = queries.length;

    // Step 1: Sort queries by start index to process efficiently
    queries.sort((a, b) => a[0] - b[0]);

    // Initialize heaps to track available and active queries
    const available = new MaxHeap(); // Max-heap for available queries' end points
    const running = new MinHeap();   // Min-heap for currently active queries' end points

    let queryIndex = 0; // Tracks which queries have been processed

    // Step 2: Iterate through `nums` to determine required decrements
    for (let i = 0; i < n; i++) {
        // Add all queries starting at or before index `i` to the available heap
        while (queryIndex < m && queries[queryIndex][0] <= i) {
            available.insert(queries[queryIndex][1]); // Store end indices in max-heap
            queryIndex++;
        }

        // Remove queries from running heap that ended before index `i`
        while (!running.isEmpty() && running.peek() < i) {
            running.extractMin();
        }

        // Apply queries from `running` to decrement nums[i] to zero
        while (nums[i] > running.size()) {
            // If no valid queries left, it is impossible to reach zero for `nums[i]`
            if (available.isEmpty() || available.peek() < i) {
                return -1;
            }
            // Use the best available query to cover index `i`
            running.insert(available.extractMax());
        }
    }

    // Step 3: Remaining available queries can be removed
    return available.size();
};

// MinHeap implementation (for managing active queries)
class MinHeap {
    constructor() {
        this.heap = [];
    }

    insert(val) {
        this.heap.push(val);
        this._heapifyUp();
    }

    extractMin() {
        if (this.heap.length === 0) return null;
        const min = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this._heapifyDown();
        }
        return min;
    }

    peek() {
        return this.heap[0] || null;
    }

    size() {
        return this.heap.length;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    _heapifyUp() {
        let idx = this.heap.length - 1;
        const element = this.heap[idx];
        while (idx > 0) {
            let parentIdx = Math.floor((idx - 1) / 2);
            let parent = this.heap[parentIdx];
            if (element >= parent) break;
            this.heap[idx] = parent;
            idx = parentIdx;
        }
        this.heap[idx] = element;
    }

    _heapifyDown() {
        let idx = 0;
        while (true) {
            let leftIdx = 2 * idx + 1;
            let rightIdx = 2 * idx + 2;
            let smallest = idx;

            if (leftIdx < this.heap.length && this.heap[leftIdx] < this.heap[smallest]) {
                smallest = leftIdx;
            }
            if (rightIdx < this.heap.length && this.heap[rightIdx] < this.heap[smallest]) {
                smallest = rightIdx;
            }
            if (smallest === idx) break;

            [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
            idx = smallest;
        }
    }
}

// MaxHeap implementation (for managing available queries)
class MaxHeap {
    constructor() {
        this.heap = [];
    }

    insert(val) {
        this.heap.push(val);
        this._heapifyUp();
    }

    extractMax() {
        if (this.heap.length === 0) return null;
        const max = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this._heapifyDown();
        }
        return max;
    }

    peek() {
        return this.heap[0] || null;
    }

    size() {
        return this.heap.length;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    _heapifyUp() {
        let idx = this.heap.length - 1;
        const element = this.heap[idx];
        while (idx > 0) {
            let parentIdx = Math.floor((idx - 1) / 2);
            let parent = this.heap[parentIdx];
            if (element <= parent) break;
            this.heap[idx] = parent;
            idx = parentIdx;
        }
        this.heap[idx] = element;
    }

    _heapifyDown() {
        let idx = 0;
        while (true) {
            let leftIdx = 2 * idx + 1;
            let rightIdx = 2 * idx + 2;
            let largest = idx;

            if (leftIdx < this.heap.length && this.heap[leftIdx] > this.heap[largest]) {
                largest = leftIdx;
            }
            if (rightIdx < this.heap.length && this.heap[rightIdx] > this.heap[largest]) {
                largest = rightIdx;
            }
            if (largest === idx) break;

            [this.heap[idx], this.heap[largest]] = [this.heap[largest], this.heap[idx]];
            idx = largest;
        }
    }
}