Zero array transformation ii

Array Binary Search Prefix Sum

43.6% acceptance

Feb 24, 2026

1023

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_zero_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
    let n = nums.len();
    let q = queries.len();
    
    let can_zero = |k: usize| -> bool {
      let mut diff = vec![0i64; n + 1];
      for i in 0..k {
        let l = queries[i][0] as usize;
        let r = queries[i][1] as usize;
        let v = queries[i][2] as i64;
        diff[l] += v;
        diff[r + 1] -= v;
      }
      let mut coverage = 0i64;
      for i in 0..n {
        coverage += diff[i];
        if coverage < nums[i] as i64 { return false; }
      }
      true
    };
    
    if can_zero(0) { return 0; } // nums is already zero
    if !can_zero(q) { return -1; }
    
    // Binary search on k
    let mut lo = 1usize;
    let mut hi = q;
    while lo < hi {
      let mid = (lo + hi) / 2;
      if can_zero(mid) { hi = mid; } else { lo = mid + 1; }
    }
    lo as i32
  }
}