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.
Example 1:
Input: nums = [0,2]
Output: 1
Explanation:
[1,1] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0].Example 2:
Input: nums = [3,1,2,1]
Output: 3
Explanation:
[1,3] (which is [1,2,1]), where the minimum non-negative integer is 1. Setting all occurrences of 1 to 0 results in [3,0,2,0].[2,2] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [3,0,0,0].[0,0] (which is [3]), where the minimum non-negative integer is 3. Setting all occurrences of 3 to 0 results in [0,0,0,0].Example 3:
Input: nums = [1,2,1,2,1,2]
Output: 4
Explanation:
[0,5] (which is [1,2,1,2,1,2]), where the minimum non-negative integer is 1. Setting all occurrences of 1 to 0 results in [0,2,0,2,0,2].[1,1] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,2,0,2].[3,3] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,0,0,2].[5,5] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,0,0,0].
Constraints:
1 <= n == nums.length <= 1050 <= nums[i] <= 105Problem Overview: You are given an integer array and need to determine the minimum number of operations required to reduce every element to zero. Each operation reduces a contiguous segment in a structured way, so the challenge is minimizing redundant work while processing the array from left to right.
Approach 1: Brute Force Simulation (O(n^2) time, O(1) space)
A direct strategy simulates the operations explicitly. Iterate through the array and whenever you encounter a positive value, repeatedly apply an operation that decreases a valid contiguous segment until that element becomes zero. This often requires scanning forward to determine the segment boundary and repeating the process for each element. The method works but performs many redundant passes over the same elements. Time complexity grows to O(n^2) in the worst case, while space usage stays O(1). This approach mainly helps understand the mechanics of the operation before optimizing.
Approach 2: Greedy Difference Counting (O(n) time, O(1) space)
The key observation: you only need a new operation when the current value is greater than the previous value. If nums[i] is larger than nums[i-1], the difference represents additional operations that must start at index i. Otherwise, existing operations can continue covering the element. By iterating once through the array and summing max(nums[i] - nums[i-1], 0), you compute the exact number of operations needed. This greedy idea eliminates repeated simulation and runs in O(n) time with constant memory. The reasoning closely relates to incremental height changes in an array.
Approach 3: Monotonic Stack (O(n) time, O(n) space)
A more structured implementation uses a monotonic stack. Maintain a stack of heights representing active segments. As you iterate through the array, pop values from the stack while they are greater than the current element since those segments must terminate. If the stack is empty or the top is smaller than the current value, the difference represents new operations, so push the current value and add the required operations. The stack maintains a non-decreasing structure, making each element pushed and popped at most once. This guarantees O(n) time and O(n) space. The technique combines ideas from greedy algorithms and classic stack-based range processing.
Recommended for interviews: Start with the brute-force explanation to demonstrate understanding of the operation mechanics. Then move to the greedy insight that operations only start when heights increase. The monotonic stack implementation is the most robust form and commonly expected when the problem includes stack-based tags. It shows strong command of monotonic stack patterns and linear-time optimization.
According to the problem description, we should first convert the smallest numbers to 0, then the second smallest numbers to 0, and so on. During this process, if two numbers are separated by smaller numbers, they require an additional operation to become 0.
We can maintain a monotonically increasing stack stk from bottom to top, and traverse each number x in the array nums:
x, it means x separates the top element. We need to pop the top element and increment the answer by 1, continuing until the top element is not greater than x.x is not 0, and the stack is empty or the top element is not equal to x, then push x onto the stack.After traversal, the remaining elements in the stack all require an additional operation to become 0, so we add the size of the stack to the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(1) | Understanding the mechanics of the operations or when constraints are very small |
| Greedy Difference Counting | O(n) | O(1) | Best general solution when the operation effect can be derived from adjacent differences |
| Monotonic Stack | O(n) | O(n) | Preferred when stack patterns appear in interviews or when tracking active segments explicitly |
Minimum Operations to Convert All Elements to Zero | Brute Force | Optimal | Leetcode 3542 | MIK • codestorywithMIK • 10,721 views views
Watch 9 more video solutions →Practice Minimum Operations to Convert All Elements to Zero with our built-in code editor and test cases.
Practice on FleetCode