3356.js

/** ------------------------------------------------------------------------------
 * 
 * 3356. Zero Array Transformation II
 * Topics: Binary Search, Prefix Sum
 * https://leetcode.com/problems/zero-array-transformation-ii/description/?envType=daily-question&envId=2025-03-13
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number}
 */
var minZeroArray = function (nums, queries) {
  const n = nums.length
  const counts = new Array(n + 1).fill(0)
  let k = 0
  let sum = 0
  for (let i = 0; i < n; i++) {
    const num = nums[i]
    while (sum + counts[i] < num) {
      if (k == queries.length) return -1
      const [left, right, value] = queries[k]
      k++

      if (right < i) continue
      counts[Math.max(left, i)] += value
      counts[right + 1] -= value
    }
    sum += counts[i]
  }
  return k
}