Problem

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.

Examples

Example 1

1
2
3
4
5

Input: nums = [0,2]
Output: 1
Explanation:
* Select the subarray `[1,1]` (which is `[2]`), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in `[0,0]`.
* Thus, the minimum number of operations required is 1.

Example 2

1
2
3
4
5
6
7

Input: nums = [3,1,2,1]
Output: 3
Explanation:
* Select subarray `[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]`.
* Select subarray `[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]`.
* Select subarray `[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]`.
* Thus, the minimum number of operations required is 3.

Example 3

1
2
3
4
5
6
7
8

Input: nums = [1,2,1,2,1,2]
Output: 4
Explanation:
* Select subarray `[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]`.
* Select subarray `[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]`.
* Select subarray `[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]`.
* Select subarray `[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]`.
* Thus, the minimum number of operations required is 4.

Constraints

  • 1 <= n == nums.length <= 10^5
  • 0 <= nums[i] <= 10^5

Method 1 – Naive Disjoint Subarray Counting

Intuition

The key idea is that we can only remove the minimum value of a subarray in one operation. For each unique value greater than zero, we need to count how many disjoint subarrays are needed to cover all its occurrences. Each block of consecutive occurrences can be removed in one operation.

Approach

  1. For each unique value x > 0 in nums, find all its positions.
  2. Count the number of disjoint blocks (consecutive runs) of x in the array.
  3. For each block, increment the operation count.
  4. Sum the counts for all unique values to get the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int minOperations(vector<int>& nums) {
        unordered_map<int, vector<int>> pos;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0) pos[nums[i]].push_back(i);
        }
        int ops = 0;
        for (auto& [val, indices] : pos) {
            int blocks = 1;
            for (int i = 1; i < indices.size(); ++i) {
                if (indices[i] != indices[i-1] + 1) blocks++;
            }
            ops += blocks;
        }
        return ops;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int minOperations(int[] nums) {
        Map<Integer, List<Integer>> pos = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] > 0) pos.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }
        int ops = 0;
        for (List<Integer> indices : pos.values()) {
            int blocks = 1;
            for (int i = 1; i < indices.size(); ++i) {
                if (indices.get(i) != indices.get(i-1) + 1) blocks++;
            }
            ops += blocks;
        }
        return ops;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        from collections import defaultdict
        pos = defaultdict(list)
        for i, x in enumerate(nums):
            if x > 0:
                pos[x].append(i)
        ops = 0
        for indices in pos.values():
            blocks = 1
            for i in range(1, len(indices)):
                if indices[i] != indices[i-1] + 1:
                    blocks += 1
            ops += blocks
        return ops

Complexity

  • ⏰ Time complexity: O(n * u), where u is the number of unique values in nums.
  • 🧺 Space complexity: O(n + u), for storing positions and unique values.

Method 2 – Monotonic Stack for Increasing Segments

Intuition

We can think of the array in terms of increasing segments. For every value that is greater than the last seen (and not already part of a valid subarray), we need a new operation. A monotonic stack helps track where a new operation is needed by maintaining the current segment.

Approach

  1. Initialize an empty stack and a counter for operations.
  2. Iterate through nums:
    • While the stack is not empty and the current number is less than the top, pop from the stack.
    • If the stack is empty or the current number is greater than the top, increment the operation count (if the number is greater than zero) and push the number onto the stack.
  3. Return the total operation count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int minOperations(vector<int>& nums) {
        stack<int> st;
        int ops = 0;
        for (int num : nums) {
            while (!st.empty() && num < st.top()) {
                st.pop();
            }
            if (st.empty() || num > st.top()) {
                if (num > 0) ops++;
                st.push(num);
            }
        }
        return ops;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int minOperations(int[] nums) {
        Deque<Integer> st = new ArrayDeque<>();
        int ops = 0;
        for (int num : nums) {
            while (!st.isEmpty() && num < st.peek()) {
                st.pop();
            }
            if (st.isEmpty() || num > st.peek()) {
                if (num > 0) ops++;
                st.push(num);
            }
        }
        return ops;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        st = []
        ops = 0
        for num in nums:
            while st and num < st[-1]:
                st.pop()
            if not st or num > st[-1]:
                if num > 0:
                    ops += 1
                st.append(num)
        return ops

Complexity

  • ⏰ Time complexity: O(n), each element is pushed and popped at most once.
  • 🧺 Space complexity: O(n), stack space in worst case.