3362.js

/** ------------------------------------------------------------------------------
 * 
 * 3362. Zero Array Transformation III
 * Topics: Array, Heap(Priority Queue), Prefix Sum
 * https://leetcode.com/problems/zero-array-transformation-iii/description/?envType=daily-question&envId=2025-05-22
 * 
 ------------------------------------------------------------------------------ */
var maxRemoval = function (nums, queries) {
  queries.sort((a, b) => a[0] - b[0])

  const heap = new MaxPriorityQueue()
  const deltaArray = Array.from({ length: nums.length + 1 }, () => 0)
  let operations = 0

  for (let i = 0, j = 0; i < nums.length; i++) {
    operations += deltaArray[i]
    while (j < queries.length && queries[j][0] === i) {
      heap.push(queries[j][1])
      j++
    }
    while (operations < nums[i] && !heap.isEmpty() && heap.front() >= i) {
      operations += 1
      deltaArray[heap.pop() + 1] -= 1
    }
    if (operations < nums[i]) {
      return -1
    }
  }
  return heap.size()
}

console.log(
  maxRemoval(
    [2, 0, 2],
    [
      [0, 2],
      [0, 2],
      [1, 1],
    ],
  ),
)