Zero array transformation iii

Array Greedy Sorting Heap (Priority Queue) Prefix Sum

54.9% acceptance

Feb 24, 2026

691

126

You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri]. 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 1. The amount by which the 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 maximum number of elements that can be removed from queries, such that nums can still be converted to a zero array using the remaining queries. If it is not possible to convert nums to a zero array, return -1.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

use std::collections::BinaryHeap;

impl Solution {
  pub fn max_removal(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
    let n = nums.len();
    let q = queries.len();
    
    // Greedy: process positions left to right.
    // At each position i, we can use queries whose l <= i.
    // We maintain a max-heap of right endpoints of usable queries.
    // If coverage at i is insufficient, greedily pick query with largest r (covers furthest right).
    // Count how many we actually use; answer = q - used.
    
    // Sort queries by left endpoint
    let mut sorted_q: Vec<(i32, i32)> = queries.iter().map(|q| (q[0], q[1])).collect();
    sorted_q.sort_unstable();
    
    let mut diff = vec![0i32; n + 1];
    let mut coverage = 0i32;
    let mut heap: BinaryHeap<i32> = BinaryHeap::new(); // max-heap of right endpoints
    let mut qi = 0;
    let mut used = 0;
    
    for i in 0..n {
      // Add all queries with l <= i to heap
      while qi < q && sorted_q[qi].0 <= i as i32 {
        heap.push(sorted_q[qi].1);
        qi += 1;
      }
      coverage += diff[i];
      // While coverage < nums[i], pick query with largest r endpoint
      while coverage < nums[i] {
        // Pop largest r that covers i (r >= i)
        loop {
          match heap.peek() {
            Some(&r) if r < i as i32 => { heap.pop(); }
            Some(_) => break,
            None => return -1,
          }
        }
        if heap.is_empty() { return -1; }
        let r = heap.pop().unwrap();
        if r < i as i32 { return -1; }
        coverage += 1;
        if (r as usize + 1) < n + 1 { diff[r as usize + 1] -= 1; }
        used += 1;
      }
    }
    
    (q as i32) - used
  }
}