3542. Minimum Operations to Convert All Elements to Zero

MediumStackGreedyArrayHash TableMonotonic Stack

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an array nums of size n, consisting of non-negative integers. Your task is to apply some (possibly zero) operations on the array so that all elements become 0.

In one operation, you can select a subarray [i, j] (where 0 <= i <= j < n) 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 in the array 0.

In simpler terms, each operation lets you pick any contiguous range of the array, find the smallest value within that range, and replace every position holding that smallest value (inside the chosen range) with 0. You want to determine the fewest such operations needed so that the entire array becomes all zeros.

The key observations behind this problem are:

It is most efficient to eliminate values in increasing order, turning the smallest remaining numbers into 0 first, then the next smallest, and so on.
Two equal values can sometimes be cleared in the same operation if they appear together without any smaller value separating them. However, if a smaller value lies between two occurrences of the same number, those occurrences are "split" and cannot be handled in a single operation, requiring an extra operation.
Any value of 0 already present needs no operation, so only positive integers contribute to the count.

Your goal is to count the minimum number of operations by carefully accounting for how values are nested and separated throughout the array.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Monotonic Stack?

This problem maps to Monotonic Stack through a short path in the full flowchart.

The problem clears array elements by removing the minimum value in a subarray; a monotonic stack tracks open value groups, each requiring one operation when closed by a smaller value.

Open in Flowchart

Intuition

Let's think about how to clear the array with as few operations as possible. Since each operation targets the minimum value within a chosen range, it makes sense to clear values from smallest to largest. Once the smallest values become 0, we can focus on the next smallest, and so on.

Now the central question becomes: when can multiple positions be cleared together in a single operation, and when do they force separate operations?

Consider a single positive value v. If all occurrences of v are contiguous (or only separated by values that are larger or already zero), we can pick a subarray covering them and clear them all in one operation. But if a smaller value sits between two occurrences of v, those two groups of v are "split" — any subarray spanning both would have that smaller value as its minimum, not v. So the two groups must be cleared by separate operations.

This "splitting" idea is exactly what a monotonic stack captures. As we scan the array left to right, we keep a stack of values that are still "open" (waiting to be cleared), arranged so that they increase from bottom to top. For each new number x:

If the top of the stack is larger than x, that larger value can no longer be extended further right without crossing a smaller barrier. It is now "closed off," so we pop it and count 1 operation for it. We keep popping while the top stays larger than x.
After popping, if x is positive and either the stack is empty or the top differs from x, we push x. The reason we skip pushing when the top equals x is that this x can join the existing identical group and be cleared in the same operation — no extra cost.

Why does popping a larger value cost an operation right away? Because encountering a smaller x proves that the larger value's region has ended; whatever amount of that larger value was accumulated before this point forms one isolated block that needs its own operation.

By the time we finish scanning, whatever values remain on the stack were never "interrupted" by a smaller value to their right. Each of these still represents one group that needs clearing, so we add the stack's size to our answer.

Putting it together: every time a value gets cut off by a smaller neighbor it contributes an operation (the pops), and every surviving group at the end contributes one more (the remaining stack). The total count gives the minimum number of operations, because equal adjacent values are merged for free while smaller-value barriers correctly force the extra operations they truly require.

Pattern Learn more about Stack, Greedy and Monotonic Stack patterns.

Solution Approach

We use a Monotonic Stack to implement the idea described above. The stack stk is maintained so that its values are monotonically increasing from bottom to top, and it holds the positive values that are still waiting to be cleared. We also keep a counter ans for the number of operations.

We traverse each number x in nums and perform the following steps:

Pop larger values (counting operations). While the stack is non-empty and the top element stk[-1] is greater than x, it means x acts as a smaller barrier that cuts off the larger value on top. That larger value's block is now finalized, so we pop it and increment ans by 1:
```
while stk and stk[-1] > x:
    ans += 1
    stk.pop()
```
This loop continues until the top element is no longer greater than x, ensuring every larger value separated by x is accounted for.
Push x if needed. After popping, if x is positive and either the stack is empty or its top is not equal to x, we push x onto the stack:
```
if x and (not stk or stk[-1] != x):
    stk.append(x)
```
- We skip x == 0 because zeros need no operation.
- We skip pushing when stk[-1] == x because this occurrence can merge with the existing identical group already on the stack — it costs no extra operation.
Account for the remaining stack. After the traversal finishes, any values left in the stack were never interrupted by a smaller value to their right. Each one represents an independent group that still needs one operation, so we add the stack's size to the answer:
```
ans += len(stk)
```

Finally, we return ans as the minimum number of operations.

Correctness summary: Each pop in step 1 corresponds to a block of a value that got isolated by a smaller neighbor, contributing one operation. Each surviving element in step 3 corresponds to a block that was never split, contributing one more. Equal adjacent values are merged for free by the condition in step 2, so the count is exactly the minimum number of operations required.

Complexity Analysis:

Time complexity: O(n), where n is the length of nums. Each element is pushed onto and popped from the stack at most once.
Space complexity: O(n), for the stack in the worst case (for example, a strictly increasing array).

Example Walkthrough

Let's trace through the solution approach with a small example:

nums = [3, 1, 2, 2, 1, 3]

We maintain a monotonically increasing stack stk (bottom to top) and a counter ans = 0. Let's process each element.

Initial state: stk = [], ans = 0

Step 1 — process x = 3

Pop check: stack is empty, nothing to pop.
Push check: 3 is positive and stack is empty → push it.

stk = [3], ans = 0

Step 2 — process x = 1

Pop check: top is 3 > 1 → this 1 is a smaller barrier cutting off the block of 3. Pop 3, ans += 1. Now stack is empty, stop popping.
Push check: 1 is positive and stack is empty → push it.

stk = [1], ans = 1

The single 3 on the left is now isolated — the 1 to its right proves its block ended, so it earned its own operation.

Step 3 — process x = 2

Pop check: top is 1, not greater than 2 → no pop.
Push check: 2 is positive and stk[-1] = 1 ≠ 2 → push it.

stk = [1, 2], ans = 1

Step 4 — process x = 2

Pop check: top is 2, not greater than 2 → no pop.
Push check: 2 is positive but stk[-1] = 2 == 2 → skip the push (this 2 merges with the adjacent identical group for free).

stk = [1, 2], ans = 1

The two adjacent 2s share one operation since no smaller value separates them.

Step 5 — process x = 1

Pop check: top is 2 > 1 → pop 2, ans += 1. Now top is 1, not greater than 1 → stop.
Push check: 1 is positive but stk[-1] = 1 == 1 → skip the push (merges with the existing 1 group).

stk = [1], ans = 2

The block of 2s (positions 2–3) is now closed off by the 1 to its right, costing one operation. The new 1 joins the earlier 1 for free.

Step 6 — process x = 3

Pop check: top is 1, not greater than 3 → no pop.
Push check: 3 is positive and stk[-1] = 1 ≠ 3 → push it.

stk = [1, 3], ans = 2

Final step — account for remaining stack

The stack [1, 3] holds two groups never interrupted by a smaller value to their right:

The 1 group (positions 1 and 4, merged).
The 3 group (position 5).

Add len(stk) = 2 to the answer:

ans = 2 + 2 = 4

Result: 4 operations.

Sanity check on the answer (clearing smallest first):

Clear all 1s: subarray [1, 4] has minimum 1 → set both 1s to 0. Array becomes [3, 0, 2, 2, 0, 3]. (1 op)
Clear the left 3 (position 0): subarray [0, 0] → [0, 0, 2, 2, 0, 3]. (1 op)
Clear the 2s: subarray [2, 3] → [0, 0, 0, 0, 0, 3]. (1 op)
Clear the right 3: subarray [5, 5] → [0, 0, 0, 0, 0, 0]. (1 op)

Total = 4 operations, matching the stack-based count.

Notice how the two 3s could not be cleared together: the smaller 1s and 2s between them split the 3s into separate blocks — exactly what the two pops/pushes of 3 captured during the scan.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def minOperations(self, nums: List[int]) -> int:
6        # Monotonic stack holding the distinct non-zero heights currently "open"
7        stack = []
8        # Total number of operations performed
9        operations = 0
10
11        for height in nums:
12            # Any height on the stack greater than the current one cannot be
13            # extended further to the right, so it must be closed off here.
14            # Each such closure counts as one operation.
15            while stack and stack[-1] > height:
16                operations += 1
17                stack.pop()
18
19            # Push the current height only if it is non-zero and differs from
20            # the stack top. A zero contributes nothing, and a duplicate of the
21            # top can be merged into the existing segment for free.
22            if height and (not stack or stack[-1] != height):
23                stack.append(height)
24
25        # Whatever remains on the stack are still-open segments, each of which
26        # requires one final operation to complete.
27        operations += len(stack)
28
29        return operations
30

1class Solution {
2    public int minOperations(int[] nums) {
3        // Monotonic stack to keep track of distinct positive heights
4        // that are currently "open" (still need to be covered by an operation).
5        Deque<Integer> stack = new ArrayDeque<>();
6
7        // Total number of operations needed.
8        int answer = 0;
9
10        for (int current : nums) {
11            // While the top of the stack is strictly greater than the current value,
12            // those heights can no longer be extended; each one requires its own operation.
13            while (!stack.isEmpty() && stack.peek() > current) {
14                answer++;
15                stack.pop();
16            }
17
18            // Push the current value only if it is positive and not a duplicate of
19            // the current top. Zeros need no operation, and equal heights can share one.
20            if (current != 0 && (stack.isEmpty() || stack.peek() != current)) {
21                stack.push(current);
22            }
23        }
24
25        // Any heights still remaining on the stack each require one operation.
26        answer += stack.size();
27
28        return answer;
29    }
30}
31

1class Solution {
2public:
3    int minOperations(vector<int>& nums) {
4        // Monotonic stack that keeps the distinct heights currently "open".
5        // Each value on the stack represents a layer that still needs one
6        // operation to be painted/cleared.
7        vector<int> stack;
8
9        // Total number of operations required.
10        int operations = 0;
11
12        for (int value : nums) {
13            // Pop every height that is strictly greater than the current value.
14            // Such layers can no longer be extended, so each of them costs
15            // one finished operation.
16            while (!stack.empty() && stack.back() > value) {
17                ++operations;
18                stack.pop_back();
19            }
20
21            // Push the current value only if it is non-zero and it differs
22            // from the top of the stack. Skipping equal values lets the same
23            // layer continue without an extra operation.
24            if (value != 0 && (stack.empty() || stack.back() != value)) {
25                stack.push_back(value);
26            }
27        }
28
29        // Any heights still left on the stack form layers that must be
30        // completed, each adding one operation.
31        operations += stack.size();
32
33        return operations;
34    }
35};
36

1/**
2 * Calculates the minimum number of operations needed,
3 * where each operation paints a contiguous segment up to a uniform height.
4 * Uses a strictly increasing monotonic stack to track active height levels.
5 *
6 * @param nums - The array of target heights.
7 * @returns The minimum number of operations.
8 */
9function minOperations(nums: number[]): number {
10    // Monotonic stack holding the currently "open" (unfinished) height levels.
11    const stack: number[] = [];
12    // Accumulates the total count of operations.
13    let ans = 0;
14
15    for (const x of nums) {
16        // Pop every height strictly greater than the current value.
17        // Each popped level is now closed off, contributing one operation.
18        while (stack.length > 0 && stack[stack.length - 1] > x) {
19            ans++;
20            stack.pop();
21        }
22
23        // Push the current value as a new height level only when:
24        //  - it is non-zero (zero requires no painting), and
25        //  - it differs from the current stack top (a repeated height
26        //    can be merged into the same operation).
27        if (x !== 0 && (stack.length === 0 || stack[stack.length - 1] !== x)) {
28            stack.push(x);
29        }
30    }
31
32    // Any heights left in the stack are still open; each needs one operation.
33    ans += stack.length;
34
35    return ans;
36}
37

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the array nums once with the outer for loop, which runs n times. Inside the loop, there is a while loop that pops elements from the stack stk. Although the while loop appears to add nested iterations, each element can be pushed onto the stack at most once and popped from the stack at most once throughout the entire execution. Therefore, the total number of push and pop operations across all iterations is bounded by O(n). Using amortized analysis, the overall time complexity is O(n), where n is the length of the array nums.

Space Complexity: O(n)

The algorithm uses a stack stk to store elements. In the worst case, when the array is strictly increasing (with no duplicates and no zeros being skipped), all n elements may be pushed onto the stack without any being popped. Thus, the stack can grow to a size of n, resulting in a space complexity of O(n), where n is the length of the array nums.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Pushing duplicate values onto the stack and double-counting equal segments

The most frequent mistake is forgetting the duplicate-merging condition in step 2. A naive implementation often pushes the current value whenever it is positive, without checking whether the stack top already equals it:

# WRONG: pushes every positive value unconditionally
for height in nums:
    while stack and stack[-1] > height:
        operations += 1
        stack.pop()
    if height:                      # missing the `stack[-1] != height` check
        stack.append(height)

operations += len(stack)

Why this is wrong: When two identical values appear consecutively (or are separated only by values that get popped away), they belong to the same segment and should be cleared in a single operation. By pushing the duplicate, the final operations += len(stack) counts the same height twice.

Example: nums = [3, 3]

Correct behavior: both 3s are part of one segment → answer is 1.
Buggy behavior: pushes 3, then pushes 3 again → stack is [3, 3] → adds 2. Wrong.

Another tricky variant — nums = [3, 1, 3]:

The 1 pops the first 3 (operations = 1), then 1 is pushed, then the second 3 is pushed → stack [1, 3] → +2 → total 3. ✅ Here the two 3s are genuinely separated by a smaller 1, so they must be two operations. The duplicate check correctly does not merge them because the first 3 was already popped before the second 3 is processed.

This illustrates why the merge check stack[-1] != height is precise: it only merges duplicates that are adjacent on the stack (i.e., not separated by a smaller barrier).

Solution: Always guard the push with both conditions:

if height and (not stack or stack[-1] != height):
    stack.append(height)

Pitfall: Mishandling zeros

Another common error is treating 0 like any other value and pushing it onto the stack, or forgetting that a 0 still acts as a barrier that pops larger values.

# WRONG: zeros pushed onto the stack inflate the final count
if not stack or stack[-1] != height:   # missing the `height` truthiness check
    stack.append(height)

Why this is wrong: A 0 requires no operation itself, but it does split larger values around it. The correct logic must:

Still run the while pop loop for 0 (so 0 closes off larger segments to its left).
Never push 0 onto the stack.

The condition if height and ... handles both: the pop loop runs unconditionally before it, and the height truthiness check prevents 0 from being pushed.

Example: nums = [2, 0, 2]

The 0 pops the first 2 (operations = 1), is not pushed, then the second 2 is pushed → stack [2] → +1 → total 2. ✅ Correct, since the two 2s are separated by a barrier and cannot share an operation.

Pitfall: Forgetting to flush the remaining stack

Finally, a subtle bug is returning operations immediately after the loop without adding len(stack):

# WRONG: segments never interrupted by a smaller value are uncounted
return operations

Values that survive to the end of the traversal were never popped, meaning no smaller barrier appeared to their right. Each still needs exactly one operation. Always add len(stack) before returning.

Example: nums = [1, 2, 3] (strictly increasing) — nothing is ever popped, so the entire answer comes from operations += len(stack) → 3.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems