Zero Array Transformation II
Source: leetcode
Difficulty: Medium
Tags: array, binary-search, prefix-sum

You are given an integer array `nums` of length `n` and a 2D array `queries` where `queries[i] = [li, ri, vali]`.


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** `vali`.
- The amount by which each value is decremented can be chosen **independently** for each index.


A **Zero Array** is an array with all its elements equal to 0\.


Return the **minimum** possible **non\-negative** value of `k`, such that after processing the first `k` queries in **sequence**, `nums` becomes a **Zero Array**. If no such `k` exists, return \-1\.


 


**Example 1:**



**Input:** nums \= \[2,0,2], queries \= \[\[0,2,1],\[0,2,1],\[1,1,3]]


**Output:** 2


**Explanation:**


- **For i \= 0 (l \= 0, r \= 2, val \= 1\):**
	- Decrement values at indices `[0, 1, 2]` by `[1, 0, 1]` respectively.
	- The array will become `[1, 0, 1]`.
- **For i \= 1 (l \= 0, r \= 2, val \= 1\):**
	- Decrement values at indices `[0, 1, 2]` by `[1, 0, 1]` respectively.
	- The array will become `[0, 0, 0]`, which is a Zero Array. Therefore, the minimum value of `k` is 2\.



**Example 2:**



**Input:** nums \= \[4,3,2,1], queries \= \[\[1,3,2],\[0,2,1]]


**Output:** \-1


**Explanation:**


- **For i \= 0 (l \= 1, r \= 3, val \= 2\):**
	- Decrement values at indices `[1, 2, 3]` by `[2, 2, 1]` respectively.
	- The array will become `[4, 1, 0, 0]`.
- **For i \= 1 (l \= 0, r \= 2, val \= 1\):**
	- Decrement values at indices `[0, 1, 2]` by `[1, 1, 0]` respectively.
	- The array will become `[3, 0, 0, 0]`, which is not a Zero Array.



 


**Constraints:**


- `1 <= nums.length <= 105`
- `0 <= nums[i] <= 5 * 105`
- `1 <= queries.length <= 105`
- `queries[i].length == 3`
- `0 <= li <= ri < nums.length`
- `1 <= vali <= 5`




C++ solution:
class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size(), sum = 0, k = 0;
        vector<int> cnt(n + 1, 0);
        for (int i = 0; i < n; i++) {
            while (sum + cnt[i] < nums[i]) {
                if (k == queries.size()) return -1;
                int l = queries[k][0];
                int r = queries[k][1];
                int val = queries[k][2];
                k++;
                
                if (r < i) continue;
                cnt[max(l, i)] += val;
                cnt[r + 1] -= val;
            }
            sum += cnt[i];
        }
        return k;
    }
};

Go solution:
func minZeroArray(nums []int, queries [][]int) int {
    qLen := len(queries)
    min := 0
    max := qLen-1
    ans := -1
    allZero := true
    for _,num := range nums {
        if num != 0 {
            allZero = false
            break
        }
    }
    if allZero {
        return 0
    }
    for min<=max {
        mid := min + (max-min)/2
        if isPossible(mid,queries,nums) {
            ans = mid
            max = mid-1
        }else{
            min = mid+1
        }
    }
    if ans != -1 {
        ans++
    }
    return ans
}

func isPossible(index int,queries [][]int,nums []int) bool{
    length := len(nums)
    pos := make([]int,length+1)
    prefix := 0
    for i:=0;i<=index;i++ {
        start := queries[i][0]
        end := queries[i][1]
        val := queries[i][2]
        pos[start] += val
        pos[end+1] -= val
    }
    for i,num := range nums {
        prefix += pos[i]
        if prefix < num {
            return false
        }
    }
    return true
}

Java solution:
class Solution {
    public int minZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] cnt = new int[n + 1];
        int s = 0, k = 0;

        for (int i = 0; i < n; ++i) {
            while (s + cnt[i] < nums[i]) {
                k++; // Increment k before accessing queries
                if (k - 1 >= queries.length) {
                    return -1;
                }
                int l = queries[k - 1][0], r = queries[k - 1][1], val = queries[k - 1][2];
                if (r < i) {
                    continue;
                }
                cnt[Math.max(l, i)] += val;
                cnt[r + 1] -= val;
            }
            s += cnt[i];
        }
        return k;
    }
}

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

    let l = -1;
    let r = m+1;
    let mid;

    while ((r-l) > 1) {
        mid = l + Math.floor((r-l)/2)
        if (isGood(mid)) {
            r = mid;
        } else {
            l = mid
        }
    }

    return r === (m+1) ? -1 : r;
    

    function isGood(k) {
        const sweepLine = new Array(n+1).fill(0);

        for (let i = 0; i < k; i++) {
            const [s, e, val] = queries[i];
            sweepLine[s] += val;
            sweepLine[e+1] -= val;
        }
        let acc = 0;

        for (let i = 0; i < n; i++) {
            acc += sweepLine[i];
            if (nums[i] > acc) {
                return false
            }
        }

        return true;
    }

};

Python solution:
class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        n = len(nums)
        cnt = [0 for _ in range(n + 1)]
        s = k = 0
        for i in range(n):
            while s + cnt[i] < nums[i]:
                k += 1
                if k - 1 >= len(queries): return -1
                l, r, val = queries[k - 1]
                if r < i: continue
                cnt[max(l, i)] += val
                cnt[r + 1] -= val
            s += cnt[i]
        return k

Ruby solution:
def min_zero_array(nums, queries)
  n = nums.size
  m = queries.size
  return 0 if nums.all? { |x| x == 0 }
  lo, hi, ans = 0, m, -1
  while lo <= hi
    mid = (lo + hi) / 2
    diff = Array.new(n, 0)
    (0...mid).each do |i|
      l, r, val = queries[i]
      diff[l] += val
      diff[r+1] -= val if r + 1 < n
    end
    curr = 0
    possible = true
    (0...n).each do |j|
      curr += diff[j]
      if curr < nums[j]
        possible = false
        break
      end
    end
    if possible
      ans = mid
      hi = mid - 1
    else
      lo = mid + 1
    end
  end
  ans
end