LeetCode Problem 3542

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Stack, Greedy, Monotonic Stack

Solution

Problem Understanding

The problem requires us to reduce all elements of a given non-negative integer array nums to zero using the fewest number of operations. Each operation allows selecting a contiguous subarray and setting all occurrences of the minimum non-negative integer in that subarray to zero. In essence, we can remove the "smallest" numbers in a segment at once, but we may need multiple operations for different values or overlapping ranges.

The input is an array of size n, with values ranging from 0 to 105. The output is a single integer representing the minimum number of operations required.

Important observations include: zeros in the array are already "done" and do not require operations. The constraints allow n to be as large as 10^5, so a naive solution that repeatedly scans the array or performs per-element operations would be too slow. Edge cases include arrays with all zeros, arrays with a single non-zero element, and arrays with alternating small and large numbers, which can challenge inefficient approaches.

Approaches

Brute Force Approach: A naive approach would repeatedly scan the array, find the minimum non-zero element, and remove it in all contiguous segments where it occurs. This would involve repeatedly scanning the array and updating it, leading to O(n^2) in the worst case because each element could require a separate scan and operation. While correct, this approach is infeasible for n = 10^5.

Optimal Approach: The key insight is that operations can be counted recursively by segmenting the array at zeros and considering each subarray separately. For any contiguous segment without zeros, the minimum element can be removed in one operation, reducing all numbers by that minimum. After subtracting the minimum, we recursively apply the same logic to segments of non-zero numbers until all elements are zero. This approach avoids unnecessary repeated scans and leverages a divide-and-conquer style operation count.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Repeatedly scans for minimum in each operation; too slow for large n
Optimal	O(n)	O(n)	Recursively reduces segments using minimums; uses recursion or stack to manage segments efficiently

Algorithm Walkthrough

1. Initialize a recursive function that takes a segment [l, r] of the array.
2. If the segment is empty or all zeros, return 0 operations.
3. Find the minimum value min_val in the segment.
4. Subtract min_val from all elements in the segment. This counts as one operation.
5. Scan the segment for contiguous subsegments of non-zero numbers.
6. Recursively apply the function to each non-zero subsegment.
7. Sum all operations from subsegments and add the operation used to subtract min_val.
8. Return the total operation count for the segment.

Why it works: By always subtracting the minimum in a segment, we guarantee that the minimum number is eliminated in the fewest steps. Recursive segmentation ensures that overlapping or isolated larger numbers are handled optimally. Each element is reduced exactly as needed, and zeros naturally divide the array into independent subproblems. We are given an array nums of length n, where each element is a non-negative integer. We may perform an operation any number of times, where an operation consists of choosing a subarray [i, j] and then identifying the minimum non-negative integer within that subarray; every occurrence of that minimum value inside the chosen subarray is set to 0.

The task is to determine the minimum number of such operations required to transform the entire array into all zeros.

The key constraint is that the operation is not a simple deletion or replacement: it depends on the minimum value inside the chosen subarray, which makes the process inherently global and order-dependent.

The input size constraint n ≤ 10^5 implies that any quadratic simulation over subarrays is infeasible, and we must reason in terms of structural properties of the array.

Edge cases include arrays already consisting entirely of zeros, arrays with strictly increasing or decreasing values, and arrays where identical values are scattered and separated by smaller values, since these affect connectivity under the “minimum-in-subarray” rule.

Approaches

Brute Force Approach

A direct simulation would attempt to repeatedly choose valid subarrays and apply the operation greedily or exhaustively until the array becomes all zeros. In each step, one would need to consider all O(n^2) subarrays, compute their minimum in O(n) time, and simulate updates. Even with memoization, the state space is exponential because each operation changes multiple positions at once in a non-local way.

This approach is correct in principle because it directly follows the problem definition, but it is computationally impossible for n = 10^5.

Key Insight

The operation depends only on the minimum value in a chosen subarray. This implies a crucial structural property: a value v can only be removed in a region where no element smaller than v exists in that region.

Thus, elements smaller than v act as permanent barriers when considering the removal of v. Once all values less than v are conceptually treated as removed (i.e., zeroed), the remaining array is partitioned into contiguous segments, and occurrences of v inside each segment may form multiple disconnected components.

Each such connected component of value v requires exactly one operation, because no single operation can remove occurrences of v across a barrier induced by a smaller value.

This suggests a threshold-based connectivity model: for each value v, consider only indices with nums[i] ≥ v, and compute how many connected components contain occurrences of v.

We can compute this efficiently using a Disjoint Set Union (DSU) structure while processing values in decreasing order.

Complexity Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(n²) or worse	Simulates all subarrays and operations
Optimal (DSU by value threshold)	O(n α(n))	O(n)	Processes values in descending order using union-find

Algorithm Walkthrough

We construct a union-find structure over indices of the array, but we activate indices in decreasing order of their values.

We define a node as “active” once it has been processed; active nodes are connected if they are adjacent in the array. This maintains connectivity among indices whose values are at least a current threshold.

We proceed as follows:

1. We group all indices by their values, forming a map value → list of indices. This allows efficient batch activation.
2. We sort the distinct values in descending order. This ensures that when we process a value v, all indices with values greater than or equal to v are already active.
3. We initialize a DSU over indices and a boolean array active initially all false.
4. We iterate over values v in descending order. For each value:

We activate all indices i such that nums[i] = v. Activation means marking active[i] = true and unioning i with its active neighbors i-1 and i+1. 5. After activation, all indices with values ≥ v are now active and connected according to adjacency. We then inspect all indices with value exactly v and compute how many distinct DSU roots they belong to. Each distinct root corresponds to one connected component of v under the constraint that values < v are removed barriers. 6. We add this count to the answer. 7. We skip value 0 since zeros require no operations.

Why it works

At threshold v, all elements smaller than v are inactive and thus act as separators, while elements greater than or equal to v preserve connectivity. Therefore, connected components of indices with value v under DSU exactly correspond to maximal subarrays where an operation can eliminate those occurrences in one step. Summing these components over all values yields the minimal number of operations.

Python Solution

from typing import List

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        def solve(l: int, r: int) -> int:
            if l > r:
                return 0
            # Find minimum in the segment
            min_val = min(nums[l:r+1])
            operations = min_val
            # Subtract min_val from the segment
            for i in range(l, r+1):
                nums[i] -= min_val
            # Recursively solve non-zero subsegments
            i = l
            while i <= r:
                if nums[i] > 0:
                    start = i
                    while i <= r and nums[i] > 0:
                        i += 1
                    operations += solve(start, i-1)
                else:
                    i += 1
            # Return min of operations by subtracting min_val and length segment method
            return min(operations, r-l+1)
        
        return solve(0, len(nums)-1)

The function solve operates on a segment [l, r]. First, it finds the segment minimum and counts one operation for reducing all numbers by that minimum. Then, it identifies contiguous non-zero subsegments and recursively applies the same logic. Finally, it compares the segment-wise minimum reduction approach against simply removing each element individually and returns the minimum. from collections import defaultdict

class DSU: def init(self, n: int): self.parent = list(range(n)) self.size = [1] * n

def find(self, x: int) -> int:
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])
    return self.parent[x]

def union(self, a: int, b: int) -> None:
    ra, rb = self.find(a), self.find(b)
    if ra == rb:
        return
    if self.size[ra] < self.size[rb]:
        ra, rb = rb, ra
    self.parent[rb] = ra
    self.size[ra] += self.size[rb]

class Solution: def minOperations(self, nums: List[int]) -> int: n = len(nums)

    value_to_indices = defaultdict(list)
    for i, v in enumerate(nums):
        value_to_indices[v].append(i)

    values = sorted(value_to_indices.keys(), reverse=True)

    dsu = DSU(n)
    active = [False] * n

    def activate(i: int) -> None:
        active[i] = True
        if i - 1 >= 0 and active[i - 1]:
            dsu.union(i, i - 1)
        if i + 1 < n and active[i + 1]:
            dsu.union(i, i + 1)

    ans = 0

    for v in values:
        if v == 0:
            continue

        for i in value_to_indices[v]:
            activate(i)

        roots = set()
        for i in value_to_indices[v]:
            roots.add(dsu.find(i))

        ans += len(roots)

    return ans

### Code Explanation

The DSU structure maintains connected components among indices that are currently active. Activation is performed in descending order of values, ensuring that at any moment, all indices with value ≥ current threshold are active.

The `activate` function connects an index to its active neighbors, preserving adjacency-based connectivity.

For each value `v`, we compute the number of distinct DSU roots among its indices. Each root represents one connected segment of `v` that can be eliminated in one operation.

## Go Solution

```go
func minOperations(nums []int) int {
    var solve func(l, r int) int
    solve = func(l, r int) int {
        if l > r {
            return 0
        }
        minVal := nums[l]
        for i := l; i <= r; i++ {
            if nums[i] < minVal {
                minVal = nums[i]
            }
        }
        operations := minVal
        for i := l; i <= r; i++ {
            nums[i] -= minVal
        }
        i := l
        for i <= r {
            if nums[i] > 0 {
                start := i
                for i <= r && nums[i] > 0 {
                    i++
                }
                operations += solve(start, i-1)
            } else {
                i++
            }
        }
        if operations > r-l+1 {
            return r-l+1
        }
        return operations
    }
    return solve(0, len(nums)-1)
}

The Go implementation mirrors the Python version. Slices are used to access segments. Go requires explicit handling of array indices and does not have built-in min for slices, so we manually compute it. Overflow is not an issue because inputs are constrained to 10^5.

Worked Examples

Example 1: nums = [0,2]

Segment [0,1], min = 0. Subtract 0 → nums unchanged. Non-zero segment [1,1], min = 2, subtract → nums = [0,0]. Operations = 1.

Example 2: nums = [3,1,2,1]

Segment [0,3], min = 1, subtract → nums = [2,0,1,0]. Non-zero segments: [0,0] min 2 → nums [0,0,1,0]; [2,2] min 1 → nums [0,0,0,0]. Total operations = 3.

Example 3: nums = [1,2,1,2,1,2]

Segment [0,5], min 1 → nums [0,1,0,1,0,1]. Non-zero segments: [1,1] min 1 → [0,0,0,1,0,1]; [3,3] min 1 → [0,0,0,0,0,1]; [5,5] min 1 → [0,0,0,0,0,0]. Operations = 4. package main

type DSU struct { parent []int size []int }

func newDSU(n int) *DSU { parent := make([]int, n) size := make([]int, n) for i := 0; i < n; i++ { parent[i] = i size[i] = 1 } return &DSU{parent: parent, size: size} }

func (d *DSU) find(x int) int { if d.parent[x] != x { d.parent[x] = d.find(d.parent[x]) } return d.parent[x] }

func (d *DSU) union(a, b int) { ra, rb := d.find(a), d.find(b) if ra == rb { return } if d.size[ra] < d.size[rb] { ra, rb = rb, ra } d.parent[rb] = ra d.size[ra] += d.size[rb] }

func minOperations(nums []int) int { n := len(nums)

type pair struct {
	val int
	idx int
}

valueToIndices := make(map[int][]int)
valuesMap := make(map[int]bool)

for i, v := range nums {
	valueToIndices[v] = append(valueToIndices[v], i)
	valuesMap[v] = true
}

values := make([]int, 0, len(valuesMap))
for v := range valuesMap {
	values = append(values, v)
}

// simple insertion sort for clarity (n distinct values small enough constraint-wise)
for i := 1; i < len(values); i++ {
	j := i
	for j > 0 && values[j] > values[j-1] {
		values[j], values[j-1] = values[j-1], values[j]
		j--
	}
}

dsu := newDSU(n)
active := make([]bool, n)

activate := func(i int) {
	active[i] = true
	if i > 0 && active[i-1] {
		dsu.union(i, i-1)
	}
	if i+1 < n && active[i+1] {
		dsu.union(i, i+1)
	}
}

ans := 0

for _, v := range values {
	if v == 0 {
		continue
	}

	for _, i := range valueToIndices[v] {
		activate(i)
	}

	seen := make(map[int]bool)
	for _, i := range valueToIndices[v] {
		seen[dsu.find(i)] = true
	}

	ans += len(seen)
}

return ans

}

### Go-specific Notes

Go requires explicit memory initialization for DSU arrays and uses maps for grouping indices. Since Go does not have built-in set structures, we use `map[int]bool` to count distinct DSU roots.

## Worked Examples

### Example 1: `nums = [0,2]`

We group indices: `0 → [0]`, `2 → [1]`.

We process values in descending order: `2, 0`.

For `2`, we activate index `1`. It forms one isolated component, so we add `1`.

Final answer is `1`.

### Example 2: `nums = [3,1,2,1]`

Value groups:

- `3 → [0]`
- `2 → [2]`
- `1 → [1,3]`

Processing:

- Activate `3`: one component → `+1`
- Activate `2`: one component → `+1`
- Activate `1`: indices `1` and `3` are not connected through ≥1 barriers, so two components → `+2`

Total = `3`.

### Example 3: `nums = [1,2,1,2,1,2]`

Groups:

- `2 → [1,3,5]`
- `1 → [0,2,4]`

Processing:

- Activate `2`: each index isolated → `3`
- Activate `1`: all indices active, but split by structure yields `3` components → `3`

Total = `6` operations? However, after DSU connectivity, components for `1` reduce because adjacency merges via ≥1 nodes; final computed correctly yields `1 component per separated segment of 1 after 2-level activation`, matching incremental removal logic.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n) | Each element is processed at most twice: once to subtract min_val and once during segmentation |
| Space | O(n) | Recursion stack depth can reach n in worst case (all elements non-zero) |

The algorithm is efficient because each subtraction eliminates at least one element's value, and the recursive segmentation avoids unnecessary repeated scans.
| Time | O(n α(n)) | Each index is activated once and union-find operations are near constant time |
| Space | O(n) | DSU arrays and auxiliary structures store parent, size, and grouping |

The algorithm avoids enumerating subarrays by reducing the problem to dynamic connectivity under value thresholds.

## Test Cases

Provided examples

assert Solution().minOperations([0,2]) == 1 # minimal non-zero element assert Solution().minOperations([3,1,2,1]) == 3 # mixed values with repeats assert Solution().minOperations([1,2,1,2,1,2]) == 4 # alternating pattern

Edge cases

assert Solution().minOperations([0,0,0]) == 0 # all zeros assert Solution().minOperations([5]) == 1 # single element assert Solution().minOperations([2,2,2,2]) == 1 # all identical non-zero assert Solution().minOperations([1,3,1,3,1]) == 3 # non-trivial alternating assert Solution().minOperations([0, 2]) == 1 # single positive element assert Solution().minOperations([3, 1, 2, 1]) == 3 # mixed ordering assert Solution().minOperations([1, 2, 1, 2, 1, 2]) == 4 # alternating pattern assert Solution().minOperations([0, 0, 0]) == 0 # already all zeros assert Solution().minOperations([5]) == 1 # single element assert Solution().minOperations([1, 1, 1]) == 1 # uniform values assert Solution().minOperations([2, 1, 2]) == 2 # smaller splits larger value

| Test | Why |
| --- | --- |
| [0,2] | Small array with one zero |
| [3,1,2,1] | Multiple operations needed, duplicates |
| [1,2,1,2,1,2] | Alternating values testing recursion |
| [0,0,0] | All zeros edge case |
| [5] | Single element |
| [2,2,2,2] | All identical non-zero elements |
| [1,3,1,3,1] | Non-trivial alternating pattern |

## Edge Cases

**All zeros:** An array of zeros should return 0 immediately. Our solution handles this because the minimum subtraction is zero, and recursion skips non-zero subsegments.

**Single element:** A single non-zero element requires exactly one operation. The recursion correctly identifies the segment `[0,0]` and counts one operation.

**Alternating high and low numbers:** Arrays like `[1,3,1,3,1]` can create multiple non-zero segments after the first subtraction. The algorithm correctly segments and counts operations recursively, ensuring no overcounting.

These edge cases validate that the solution is
| `[0,2]` | simplest non-trivial case |
| `[3,1,2,1]` | multiple values and interleaving |
| `[1,2,1,2,1,2]` | alternating fragmentation stress |
| `[0,0,0]` | already solved state |
| `[5]` | single-element boundary |
| `[1,1,1]` | uniform values |
| `[2,1,2]` | separator effect of smaller values |

## Edge Cases

One important edge case is an array consisting entirely of zeros. Since no operation can meaningfully reduce values below zero and operations targeting zero do not change the array, the correct answer is immediately zero. The algorithm handles this by skipping value `0` entirely and never activating or counting it.

Another edge case is a single-element array. In this case, if the element is non-zero, exactly one operation suffices because the entire array is a valid subarray whose minimum is that element. The DSU approach correctly produces one connected component for that value.

A third edge case involves repeated identical values separated by smaller values. These smaller values act as permanent barriers at the time of processing larger thresholds, ensuring that identical values split into multiple DSU components. The algorithm correctly accounts for each disconnected segment as requiring a separate operation, since no single valid subarray can bridge across a smaller element.