Problem Statement in English

You’re given a 0-indexed array nums of non-negative integers. In one operation, you can pick a subarray of nums and make the smallest element in that subarray equal to 0.

Return the minimum number of operations required to convert all elements of nums to 0.

Approach

I really feel that coming up with this intuitively is… quite hard. There are some observations that we need to make.

If a subarray of numbers has 0s on its left and right, then at best we can select that interior subarray and make its smallest element, and all its occurences in that subarray 0 in one operation.

So we can think of this problem as splitting the array into segments separated at local minima.

If we have a local minima, and elements to its left that are larger than it, then the previous segment ends at the current index. So we keep popping elements from the stack until we find an element that is $<=$ than the current element. If it’s equal, we don’t need to add the current element again since it will form a segment with the same minimum, i.e., we don’t need to do a new operation since it will be covered by the previous segment. For example in [1,2,1], the two 1s can be covered in one operation, and the 2 will be covered in another operation.

We also need to handle 0s specially, since they can be covered in no operations. So we just skip them. However, the 0 does count towards splitting segments. Just that we don’t use it in the stack, or count it as an operation.

This is a monotonic increasing stack approach.

I know I’ve not done a good job explaining this, so I recommend watching NeetCode’s video, and maybe just reading the code.

Solution in Python


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

        for n in nums:
            while stack and stack[-1] > n:
                stack.pop()

            if not n:
                continue

            if stack and stack[-1] == n:
                continue

            res += 1
            stack.append(n)

        return res

Complexity

  • Time: $O(n)$
    Since we are iterating through the array once and each element is pushed and popped at most once from the stack.

  • Space: $O(n)$
    The space complexity is $O(n)$ due to the stack used to keep track of elements.

Mistakes I Made

I had to watch NeetCode’s solution video

And we are done.