Zero array transformation i

Array Prefix Sum

54.4% acceptance

Feb 24, 2026

848

You are given an integer array nums of length n and a 2D array queries, where queries[i] = [li, ri]. For each queries[i]: Select a subset of indices within the range [li, ri] in nums. Decrement the values at the selected indices by 1. A Zero Array is an array where all elements are equal to 0. Return true if it is possible to transform nums into a Zero Array after processing all the queries sequentially, otherwise return false.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_zero_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> bool {
    let n = nums.len();
    // Each query [l,r] can decrement any subset of indices in [l,r] by 1.
    // So query [l,r] provides at most 1 decrement for each position in [l,r].
    // Total available decrements at position i = count of queries covering i.
    // Feasible iff for all i: count_of_covering_queries[i] >= nums[i].
    
    let mut diff = vec![0i32; n + 1];
    for q in &queries {
      let l = q[0] as usize;
      let r = q[1] as usize;
      diff[l] += 1;
      diff[r + 1] -= 1;
    }
    let mut coverage = 0i32;
    for i in 0..n {
      coverage += diff[i];
      if coverage < nums[i] { return false; }
    }
    true
  }
}