Minimum operations to convert all elements to zero

Array Hash Table Stack Greedy Monotonic Stack

53.0% acceptance

Feb 25, 2026

613

You are given an array nums of non-negative integers. In one operation, select a subarray [i,j] and set all occurrences of the minimum non-negative integer in that subarray to 0. Return the minimum number of operations required to make all elements 0.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(nums: Vec<i32>) -> i32 {
    // Monotonic stack approach O(n):
    // Traverse nums. Maintain an increasing stack of "active" values.
    // - If x == 0: clear the stack (0 separates everything).
    // - While stack top > x: pop (those groups have ended).
    // - If stack is empty or top < x: push x and increment ops
    //   (a new group for value x starts here).
    // - If top == x: do nothing (continuing the same group).
    // Each push represents exactly one required operation.
    let mut stack: Vec<i32> = Vec::new();
    let mut ops = 0;
    for x in nums {
      if x == 0 {
        stack.clear();
      } else {
        while stack.last().map_or(false, |&top| top > x) {
          stack.pop();
        }
        if stack.last().map_or(true, |&top| top < x) {
          stack.push(x);
          ops += 1;
        }
        // top == x: same group, no push
      }
    }
    ops
  }
}