Zero Array Transformation II - Line Sweep, Binary Search [JS]

Description 

Solution 1: Binary Search & Line Sweep

Binary search for the minimum k, where nums becomes a zero array after k queries.
To check whether a value k is valid,

• Use line sweep to accumulate updates on every range.
• Accumulate them at the end using prefix sum and check that every nums[i] <= 0.

n = length of nums, m = number of queries
Time Complexity: O(n log(m))
Space Complexity: O(n)

JavaScript

function minZeroArray(nums, queries) {
  const m = queries.length;
  let low = 0, high = m;
  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (isValid(nums, queries, mid)) high = mid;
    else low = mid + 1;
  }
  return isValid(nums, queries, low) ? low : -1;
};

function isValid(nums, queries, k) {
  const n = nums.length, updates = Array(n + 1).fill(0);
  for (let i = 0; i < k; i++) {
    const [l, r, val] = queries[i];
    updates[l] -= val;
    updates[r + 1] += val;
  }
  let sum = 0, updateSum = 0;
  for (let i = 0; i < n; i++) {
    updateSum += updates[i];
    sum += Math.max(0, nums[i] + updateSum);
  }
  return sum === 0;
}

---

Solution 2: Line Sweep & Two Pointers

In the end, all numbers need to become 0.
So, go through every index from 0 to n-1 and apply queries while nums[i] is not yet 0.
We don't apply any queries unless nums[i] > 0.

Apply range updates using line sweep and prefix sum.
Compute the prefix sum for range updates on the fly as we move i forward.

Time Complexity: O(n + m)
Space Complexity: O(n)

JavaScript

function minZeroArray(nums, queries) {
  const n = nums.length, m = queries.length;  
  const updates = Array(n + 1).fill(0);
  let updateSum = 0, j = 0;
  for (let i = 0; i < n; i++) {
    updateSum += updates[i];
    while (nums[i] + updateSum > 0 && j < m) {
      const [l, r, val] = queries[j];
      if (l <= i && r >= i) updateSum -= val; // query starts before or at this index, hence we need to add directly to running sum.
      if (l > i) updates[l] -= val; // no point adding update to an index we have already passed.
      if (r >= i) updates[r + 1] += val; // no point adding update to an index we have already passed.
      j++;
    }
    if (nums[i] + updateSum > 0 && j === m) {
      return -1;
    }
  }
  return j;
};