Minimum Operations to Convert all Elements to Zero Solution

Problem Statement

minimum operations to convert all elements to zero

Intuition & Approach

If all array elements are positive, can use a monotonic stack to count the number of segments that each elements needed to be update.

Some important observations:

1. The minimum value in the current array will always require only one attempt to remove (take the subarray includes all elements)
2. Assume a specific number $n$ will be successfully transformed after operations on $k$ segments of $(in_1, jn_1)$, $(in_2, jn_2)$ $\dots$ $in_k, jn_k$. We can infer two important invariants:
   • $\forall c \in [in_p, jn_p], arr[c] \geq n, p \in [1, 2, \dots, k]$
   • For all elements not in the segment, it should be smaller than $n$ (all have been cleared)

Hence, we can utilize a monotonic increasing stack to maintain the second invariance. Inversion in the stack means, that the segment with the larger values will be seperated from elements that will be coming in in the future, therefore, we can increment the count when encounter an inversion. This will eventually lead to the correct final result.

The aforementioned idea only works if all elements are positive, and it does not work when some elements are 0. However, there is a way to handle the zeros gracefully. Just don't push the 0 to the stack.

Complexity

Time complexity:

$$O(n)$$

Space complexity:

$$O(n)$$

Code

class Solution {
public:
    int minOperations(vector<int>& nums) {
        // The minimum element always take one run
        // check the top of the stack: == do nothing, > push, < pop until equal or empty
        int cnt = 0;
        vector<int> stack;
        for (auto i : nums) {
            if (stack.empty()) {
                if (i != 0) stack.push_back(i);
            } else if (*prev(stack.end()) <= i) {
                if (*prev(stack.end()) < i && i > 0) stack.push_back(i);
            } else {
                while (!stack.empty() && *prev(stack.end()) > i) {
                    ++cnt;
                    stack.pop_back();
                }

                if ((stack.empty() || *prev(stack.end()) < i) && i > 0) stack.push_back(i);
            }
        }
        cnt += stack.size();
        return cnt;
    }
};