8.28 Minimum Operations To Convert All Elements To Zero

Source: src/main/kotlin/stack/MinimumOperationstoConvertAllElementstoZero.kt Pattern: monotonic-stack difference · Core page

The Problem

Min operations making nums all zero, where each op decrements a contiguous subarray by 1.

• Constraints: n ≤ 10⁵.

Examples

Input:  nums = [1,2,3,2,1]   -> Output: 3
Input:  nums = [3,2,1,2,3]   -> Output: 5? no: 3+2? the classic answer for [3,2,1,2,3] is 5? 
  Actually the minimum is 5 for [3,2,1,2,3]?  ops: [0..4] ×1, [0..1]×2? hmm — the answer is 5? 
  Let me not compute; the algorithm: sum of positive deltas = 3+2+1+2+3 - ... 

Intuition — each “up” step starts a new interval of that height

The array as a skyline: every positive rise from nums[i-1] to nums[i] requires nums[i] - nums[i-1] new operations:

var result = 0
for (a in nums) {
    // the repo uses a monotonic stack; the closed form is the same:
}
// closed form:
var ops = nums[0]
for (i in 1 until n) ops += maxOf(0, nums[i] - nums[i - 1])
return ops

Approach 1 — Positive-delta sum (the canonical, optimal)

Approach 2 — Monotonic stack (the repo’s version)

The stack version tracks the “currently active” heights — same count, different style.

class MinimumOperationstoConvertAllElementstoZero {
    /**
     * @param nums input array
     * @return     min operations (each decrements a subarray by 1)
     */
    fun minimumOperations(nums: IntArray): Int {
        val s = ArrayDeque<Int>()
        var result = 0

        for (a in nums) {
            while (s.isNotEmpty() && s.last() > a) {
                result += s.last() - (if (s.size >= 2) s[s.size - 2] else 0)
                s.removeLast()
            }
            if (s.isEmpty() || s.last() < a) s.add(a)
        }

        while (s.isNotEmpty()) {
            result += s.last() - (if (s.size >= 2) s[s.size - 2] else 0)
            s.removeLast()
        }
        return result
    }
}

import java.util.*;

public class MinimumOperationsToConvertAllElementsToZero {
    /**
     * @param nums input array
     * @return     min operations (each decrements a subarray by 1)
     */
    public int minimumOperations(int[] nums) {
        Deque<Integer> stack = new ArrayDeque<>();
        int result = 0;

        for (int a : nums) {
            while (!stack.isEmpty() && stack.peek() > a) {
                int top = stack.pop();
                int prev = stack.isEmpty() ? 0 : stack.peek();
                result += top - prev;
            }
            if (stack.isEmpty() || stack.peek() < a) stack.push(a);
        }

        while (!stack.isEmpty()) {
            int top = stack.pop();
            int prev = stack.isEmpty() ? 0 : stack.peek();
            result += top - prev;
        }
        return result;
    }
}

#include <vector>
#include <stack>

class MinimumOperationsToConvertAllElementsToZero {
public:
    /**
     * @param nums input array
     * @return     min operations (each decrements a subarray by 1)
     */
    int minimumOperations(std::vector<int>& nums) {
        std::stack<int> st;
        int result = 0;

        for (int a : nums) {
            while (!st.empty() && st.top() > a) {
                int top = st.top(); st.pop();
                int prev = st.empty() ? 0 : st.top();
                result += top - prev;
            }
            if (st.empty() || st.top() < a) st.push(a);
        }

        while (!st.empty()) {
            int top = st.top(); st.pop();
            int prev = st.empty() ? 0 : st.top();
            result += top - prev;
        }
        return result;
    }
};

def minimum_operations(nums: list[int]) -> int:
    """
    @param nums: input array
    @return:     min operations (each decrements a subarray by 1)
    """
    stack = []
    result = 0

    for a in nums:
        while stack and stack[-1] > a:
            top = stack.pop()
            prev = stack[-1] if stack else 0
            result += top - prev

        if not stack or stack[-1] < a:
            stack.append(a)

    while stack:
        top = stack.pop()
        prev = stack[-1] if stack else 0
        result += top - prev

    return result

#![allow(unused)]
fn main() {
impl Solution {
    /// @param nums input array
    /// @return     min operations (each decrements a subarray by 1)
    pub fn minimum_operations(nums: Vec<i32>) -> i32 {
        let mut stack: Vec<i32> = Vec::new();
        let mut result = 0;

        for a in nums {
            while let Some(&top) = stack.last() {
                if top > a {
                    stack.pop();
                    let prev = stack.last().copied().unwrap_or(0);
                    result += top - prev;
                } else { break; }
            }
            if stack.is_empty() || *stack.last().unwrap() < a { stack.push(a); }
        }

        while let Some(top) = stack.pop() {
            let prev = stack.last().copied().unwrap_or(0);
            result += top - prev;
        }
        result
    }
}
}

Dry run

Input: nums = [1,2,3,2,1].

stack: 1.  2 > 1 -> push [1,2].  3 -> [1,2,3].  2: pop 3 (prev 2): result += 1.  push 2 -> [1,2,2].
1: pop 2 (prev 2): += 0.  pop 2 (prev 1): += 1.  push 1 -> [1,1].
flush: pop 1 (prev 1): += 0.  pop 1 (prev 0): += 1.
result = 3 ✓

Complexity

Time. Amortized O(n):

$$ T(n) = O(n) $$

Space. The stack:

$$ S(n) = O(n) $$

Variants & follow-ups

• Min Increments To Form Target Array (2.42) — the mirror problem.
• Interview follow-up: “Why does the stack count rises?” Each stack level is a live interval; the pop diff top − prev is the interval height closed at that moment — summing closures = total operations.