LeetCode Entry

3542. Minimum Operations to Convert All Elements to Zero

10.11.2025 medium 2025 kotlin rust

Min ops to zeros by making min of subarrays 0 stack

3542. Minimum Operations to Convert All Elements to Zero medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1169

Problem TLDR

Min ops to zeros by making min of subarrays 0 #medium #monotonic_stack

Intuition

    // 1 2 3 1 2 3 4 1 2 3
    // 0 2 3 0 2 3 4 0 2 3
    // 0 0 3 0 2 3 4 0 2 3
    // 0 0 0 0 2 3 4 0 2 3
    // 0 0 0 0 0 3 4 0 2 3
    // 0 0 0 0 0 0 4 0 2 3
    // 0 0 0 0 0 0 0 0 2 3
    // 0 0 0 0 0 0 0 0 0 3
    // 0 0 0 0 0 0 0 0 0 0
    //
    // 1 2 3 2 1
    // 0 2 3 2 0
    // 0 0 3 0 0
    // 0 0 0 0 0
    //
    // 3 2 1 2 3
    // 3 2 0 2 3
    // 3 0 0 2 3
    // 0 0 0 2 3
    // 0 0 0 0 3
    // 0 0 0 0 0
    //
    // 3 2 1 2 3 2 1
    // *               3
    //   *             2<3, +ops
    //     *           1<2, +ops
    //       2         2 1
    //         3       3 2 1
    //           2     2<3, +ops; 2 1
    //             1   1<2, +ops; 1
    //                 1 + ops
    //    total = 5

• each decrease means the previous value goes to the separate operation

Approach

• the remainig values in stack are all separate operations
• or, we can count increases as operations instead of decreases
• dirty trick to O(1) memory: use input array as a stack

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

// 32ms
    fun minOperations(n: IntArray): Int {
        var s = -1
        return n.count { x ->
            while (s >= 0 && n[s] > x) s--
            (x > 0 && (s < 0 || n[s] < x)).also { if (it) n[++s] = x}
        }
    }

// 12ms
    pub fn min_operations(n: Vec<i32>) -> i32 {
        let (mut r, mut s) = (0, vec![0]);
        for x in n {
            while s[s.len()-1] > x { s.pop(); }
            if s[s.len()-1] < x { r += 1; s.push(x) }
        }; r
    }