Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Equal positive values can be removed together only while no smaller value separates them: otherwise that smaller value must be removed first and becomes a zero barrier. A monotone stack tracks the increasing value levels still connected across the processed prefix.

Approach

Scan left to right. Before handling value x, pop every stack value greater than x; those larger levels can no longer connect across the current position. If x is zero, do not push it. Otherwise, if the stack is empty or its top is smaller than x, push x and count a new operation. If the top already equals x, it belongs to the same removable level and adds no operation.

Each new level needs a separate removal within its connected region. Removing minima first recursively realizes those counted levels, so the count is sufficient as well as necessary. Every value is pushed and popped at most once, and zero clears all positive levels naturally.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        s = []

        for x in nums:
            while s and s[-1] > x:
                s.pop()
            if x == 0:
                continue
            if not s or s[-1] < x:
                s.append(x)
                res += 1

        return res

Complexity analysis

Let n = nums.length. Time: O(n). Auxiliary space: O(n) for the monotonic stack.