# Minimum Operations to Convert All Elements to Zero
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-convert-all-elements-to-zero)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-convert-all-elements-to-zero
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Hash Table, Stack, Monotonic Stack
---
## 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.

**Example 1:**

**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:**

**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:**

**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 <= 105`
* `0 <= nums[i] <= 105`

# Approaches
## Simulation Approach
This approach directly simulates the process described in the problem. We handle the numbers in increasing order of their value. For each value `v`, we determine how many operations are needed to clear all of its occurrences. An operation to clear `v` requires selecting a subarray where `v` is the minimum non-negative integer. This is only possible if the subarray contains no zeros. As we process values in increasing order (`1, 2, 3, ...`), when we are at value `v`, all numbers smaller than `v` have already been turned to zero. Therefore, the zeros in the array act as separators. Occurrences of `v` that are in different contiguous blocks of non-zero numbers cannot be cleared by a single operation. Thus, for each value `v`, the number of operations required is equal to the number of distinct non-zero blocks that contain at least one `v`.
**Time:** O(U * N), where N is the number of elements and U is the number of unique non-zero values in the array. In the worst case, U can be up to N, leading to an O(N^2) complexity. The outer loop runs U times, and inside it, we iterate through the array of size N multiple times. · **Space:** O(N), where N is the number of elements in the array. This is for storing the copy of the array and the set of unique values.
**Pros:** The logic is straightforward and closely follows the problem's state changes.; It's relatively easy to implement.
**Cons:** The time complexity is high, making it unsuitable for large inputs as it will likely result in a 'Time Limit Exceeded' error.
### Explanation
The simulation proceeds value by value. We start with the smallest non-zero number and count the operations needed for it, then move to the next smallest, and so on. To count operations for a value `v`, we look at the current state of the array (where all numbers `< v` are zero). We identify contiguous segments of non-zero numbers. Each such segment that contains `v` requires one operation. After counting, we set all `v`'s to zero to simulate their removal before processing the next value.

```java
import java.util.*;

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int[] currentNums = Arrays.copyOf(nums, n);
        Set<Integer> uniqueValsSet = new HashSet<>();
        for (int num : currentNums) {
            if (num > 0) {
                uniqueValsSet.add(num);
            }
        }
        List<Integer> sortedUniqueVals = new ArrayList<>(uniqueValsSet);
        Collections.sort(sortedUniqueVals);

        int totalOperations = 0;

        for (int val : sortedUniqueVals) {
            int opsForVal = 0;
            boolean inBlock = false;
            boolean blockContainsVal = false;

            for (int i = 0; i < n; i++) {
                if (currentNums[i] > 0) {
                    if (!inBlock) {
                        inBlock = true;
                        blockContainsVal = false;
                    }
                    if (currentNums[i] == val) {
                        blockContainsVal = true;
                    }
                } else { // currentNums[i] == 0
                    if (inBlock) {
                        if (blockContainsVal) {
                            opsForVal++;
                        }
                        inBlock = false;
                    }
                }
            }
            // Check for the last block
            if (inBlock && blockContainsVal) {
                opsForVal++;
            }
            
            totalOperations += opsForVal;

            // Set all occurrences of val to 0 for the next iteration
            for (int i = 0; i < n; i++) {
                if (currentNums[i] == val) {
                    currentNums[i] = 0;
                }
            }
        }

        return totalOperations;
    }
}
```
### Algorithm
- Create a copy of the input array, `current_nums`, to modify during the simulation.
- Find all unique non-zero values in the array and sort them in ascending order.
- Initialize `total_operations = 0`.
- Iterate through each unique value `v` from smallest to largest:
  - Scan `current_nums` to identify contiguous blocks of non-zero elements.
  - For each non-zero block, check if it contains the value `v`.
  - The number of operations for `v` is the count of such blocks.
  - Add this count to `total_operations`.
  - After processing `v`, update `current_nums` by setting all occurrences of `v` to 0. This simulates the clearance of `v` and prepares the array for the next value.
- Return `total_operations`.

## Segment Tree and Grouping Approach
This approach is an optimization of the simulation. The core idea remains the same: the total number of operations is the sum of operations required for each unique value `v > 0`. The number of operations for `v` (`Ops(v)`) is the number of its occurrences that need to start a new operation. This happens when an occurrence of `v` is not in the same operational block as a preceding occurrence of `v`. Two occurrences of `v` at indices `i` and `j` (`i < j`) are in the same block if the subarray `nums[i...j]` contains no numbers that would have been zeroed out, i.e., no numbers smaller than `v`. Instead of repeatedly scanning the array, we can answer the question "is there a number smaller than `v` between two indices?" efficiently. A Segment Tree is a suitable data structure for this, allowing for O(log N) range minimum queries. After processing all occurrences of a value `v`, we update their positions in the segment tree to 0 to reflect the change in the array's state for subsequent, larger values.
**Time:** O(N log N), where N is the length of the array. Building the map and sorting unique values takes O(N log N) or O(N) depending on implementation details. The main loop iterates through unique values. The total number of range queries and updates across all values is proportional to N. Each query and update on the Segment Tree takes O(log N). Thus, the total time is dominated by segment tree operations, resulting in O(N log N). · **Space:** O(N), where N is the number of elements. This space is used for the map storing indices (O(N) in the worst case), the unique values set (O(U) where U is number of unique values), and the Segment Tree (O(N)).
**Pros:** Highly efficient with a time complexity of O(N log N), which passes for large inputs.; The approach is robust and correctly models the problem's constraints.
**Cons:** Implementation is more complex due to the need for a Segment Tree data structure.; The space complexity is higher than a simple simulation due to the Segment Tree and the map.
### Explanation
We can determine `Ops(v)` by finding the number of connected components of `v`'s indices. Two indices are in the same component if the subarray between them contains only values greater than or equal to `v`. This check can be optimized using a Segment Tree for range minimum queries.

```java
import java.util.*;

class Solution {
    // Segment Tree for Range Minimum Query
    static class SegmentTree {
        int[] tree;
        int[] nums;
        int n;

        SegmentTree(int[] nums) {
            this.n = nums.length;
            this.nums = nums;
            this.tree = new int[4 * n];
            build(0, 0, n - 1);
        }

        private void build(int node, int start, int end) {
            if (start == end) {
                tree[node] = nums[start];
            } else {
                int mid = start + (end - start) / 2;
                build(2 * node + 1, start, mid);
                build(2 * node + 2, mid + 1, end);
                tree[node] = Math.min(tree[2 * node + 1], tree[2 * node + 2]);
            }
        }

        public int query(int l, int r) {
            return query(0, 0, n - 1, l, r);
        }

        private int query(int node, int start, int end, int l, int r) {
            if (r < start || end < l) {
                return Integer.MAX_VALUE;
            }
            if (l <= start && end <= r) {
                return tree[node];
            }
            int mid = start + (end - start) / 2;
            int p1 = query(2 * node + 1, start, mid, l, r);
            int p2 = query(2 * node + 2, mid + 1, end, l, r);
            return Math.min(p1, p2);
        }

        public void update(int idx, int val) {
            update(0, 0, n - 1, idx, val);
        }

        private void update(int node, int start, int end, int idx, int val) {
            if (start == end) {
                nums[idx] = val;
                tree[node] = val;
            } else {
                int mid = start + (end - start) / 2;
                if (start <= idx && idx <= mid) {
                    update(2 * node + 1, start, mid, idx, val);
                } else {
                    update(2 * node + 2, mid + 1, end, idx, val);
                }
                tree[node] = Math.min(tree[2 * node + 1], tree[2 * node + 2]);
            }
        }
    }

    public int minOperations(int[] nums) {
        Map<Integer, List<Integer>> valToIndices = new HashMap<>();
        Set<Integer> uniqueValsSet = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                valToIndices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
                uniqueValsSet.add(nums[i]);
            }
        }

        SegmentTree st = new SegmentTree(nums);
        int totalOperations = 0;

        for (int val : uniqueValsSet) {
            List<Integer> indices = valToIndices.get(val);
            if (indices == null || indices.isEmpty()) continue;

            int groups = 1;
            for (int i = 1; i < indices.size(); i++) {
                int prevIdx = indices.get(i - 1);
                int currIdx = indices.get(i);
                if (st.query(prevIdx, currIdx) < val) {
                    groups++;
                }
            }
            totalOperations += groups;

            for (int idx : indices) {
                st.update(idx, 0);
            }
        }

        return totalOperations;
    }
}
```
### Algorithm
- Pre-process the input array to create a map from each value to a list of its indices. This takes O(N) time.
- Get a sorted list of unique non-zero values from the array.
- Build a Segment Tree on the input array. The segment tree should support range minimum queries and point updates in O(log N) time.
- Initialize `total_operations = 0`.
- Iterate through the unique values `v` in increasing order:
  - Get the list of indices for `v`.
  - The number of operations for `v`, let's call it `groups`, is at least 1 (for the first occurrence).
  - Iterate through the indices of `v` from the second one. For each pair of consecutive indices (`prev_idx`, `curr_idx`), query the segment tree for the minimum value in `nums[prev_idx...curr_idx]`.
  - If this minimum is less than `v`, it means the two occurrences are separated by a smaller number (which is now conceptually 0), so they belong to different groups. Increment `groups`.
  - Add `groups` to `total_operations`.
  - After processing `v`, update the segment tree by setting the value at each of `v`'s indices to 0. This prepares the state for the next value.
- Return `total_operations`.