Zero array transformation iv

Array Dynamic Programming

31.0% acceptance

Feb 25, 2026

142

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: Select a subset of indices in the range [li, ri] from nums. Decrement the value at each selected index by exactly vali. 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 * m)

Space O(n * m)

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 max_val = 1001usize;
    // dp[i][v] = true if we can form sum v using a subset of query values
    // seen so far that cover index i. Selecting a query's val for index i
    // is independent per query (include or exclude).
    let mut dp: Vec<Vec<bool>> = vec![vec![false; max_val]; n];
    for i in 0..n {
      dp[i][0] = true; // empty subset sums to 0
    }
    let is_zero = |dp: &Vec<Vec<bool>>| -> bool {
      for i in 0..n {
        let t = nums[i] as usize;
        if t >= max_val || !dp[i][t] { return false; }
      }
      true
    };
    if is_zero(&dp) { return 0; }
    for k in 0..q {
      let l = queries[k][0] as usize;
      let r = queries[k][1] as usize;
      let val = queries[k][2] as usize;
      for i in l..=r {
        // Knapsack-style update (iterate high to low to avoid reuse)
        for v in (0..max_val - val).rev() {
          if dp[i][v] {
            dp[i][v + val] = true;
          }
        }
      }
      if is_zero(&dp) { return (k + 1) as i32; }
    }
    -1
  }
}