Minimum Operations to Convert All Elements to Zero

medium monotonic stack greedy array

Problem

You are given an array nums of non-negative integers. In one operation you pick a subarray [i, j] and set every occurrence of the minimum non-negative value inside it to 0. Return the minimum number of operations needed to turn every element into 0.

The trick: think of the values by height. A run of equal positive values can be cleared together in one op, but a larger value sitting on top of a smaller one must be cleared in its own later op. Sweep left to right keeping a strictly increasing stack of the positive heights still "open"; each time a brand-new height opens, that's one operation.

Inputnums = [3,1,2,1]

Output3

Clear all the 1's together (1 op), then the lone 2 (1 op), then the 3 (1 op): 3 operations.

nums (comma-separated, 0..9)

def minOperations(nums):
    stack = []          # strictly increasing positive heights still "open"
    ops = 0
    for v in nums:
        # close every open height taller than v: it is fully sealed off
        while stack and stack[-1] > v:
            stack.pop()
        if v > 0:
            # a height equal to the top is the same run -> no new op
            if not stack or stack[-1] < v:
                ops += 1            # a brand-new height opens here
                stack.append(v)
    return ops

function minOperations(nums) {
  const stack = [];          // strictly increasing open positive heights
  let ops = 0;
  for (const v of nums) {
    // close every open height taller than v
    while (stack.length && stack[stack.length - 1] > v) {
      stack.pop();
    }
    if (v > 0) {
      // equal to top -> same run, no new op
      if (!stack.length || stack[stack.length - 1] < v) {
        ops++;                 // a brand-new height opens
        stack.push(v);
      }
    }
  }
  return ops;
}

int minOperations(int[] nums) {
    Deque<Integer> stack = new ArrayDeque<>(); // increasing open heights
    int ops = 0;
    for (int v : nums) {
        // close every open height taller than v
        while (!stack.isEmpty() && stack.peek() > v) {
            stack.pop();
        }
        if (v > 0) {
            // equal to top -> same run, no new op
            if (stack.isEmpty() || stack.peek() < v) {
                ops++;             // a brand-new height opens
                stack.push(v);
            }
        }
    }
    return ops;
}

int minOperations(vector<int>& nums) {
    vector<int> stack;          // increasing open positive heights
    int ops = 0;
    for (int v : nums) {
        // close every open height taller than v
        while (!stack.empty() && stack.back() > v) {
            stack.pop_back();
        }
        if (v > 0) {
            // equal to top -> same run, no new op
            if (stack.empty() || stack.back() < v) {
                ops++;             // a brand-new height opens
                stack.push_back(v);
            }
        }
    }
    return ops;
}

Explanation

Picture each positive value as a bar of that height. Equal bars that sit next to each other (with nothing shorter between them) belong to the same "run" and can all be set to zero in a single operation, because one subarray covers them and their value is the minimum there. So the question becomes: how many distinct runs must we open?

We sweep left to right and keep a strictly increasing stack of the heights that are currently "open" — meaning a run at that height has started but not yet been sealed off by a shorter bar to its right.

When the new value v arrives, any open height on the stack that is taller than v can never be extended further (the shorter bar breaks its run), so we pop those — they were already counted. Then we look at the top:

If v > 0 and the stack is empty or its top is smaller than v, this is a genuinely new height stacking on top of whatever is below, so we do ops += 1 and push v. If the top already equals v, we are still inside the same run and add nothing. Zeros simply clear the stack down and never cost an operation.

For nums = [3,1,2,1]: the 3 opens (ops 1). The first 1 pops the 3 and opens a 1 (ops 2). The 2 opens on top of the 1 (ops 3). The last 1 pops the 2 but matches the open 1 — no new op. Total = 3.

Time: O(n) Space: O(n)