I process values from largest to smallest and maintain which indices are currently active (having value ≥ current threshold) using a DSU (union–find) over indices. When I add all indices whose value equals v, I activate them and union with active neighbors so the DSU components represent contiguous segments of positions with value ≥ v. All indices with value v that end up in the same DSU root can be zeroed with one operation (choose that whole component). So for each value v I add the number of distinct DSU roots among the newly added indices to the answer. Summing over values yields the minimum number of operations.
from typing import List, Dict
class DSU:
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0]*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.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
class Solution:
def minOperations(self, nums: List[int]) -> int:
n = len(nums)
val_to_indices: Dict[int, List[int]] = {}
for i, v in enumerate(nums):
if v > 0:
val_to_indices.setdefault(v, []).append(i)
if not val_to_indices:
return 0
distinct_vals = sorted(val_to_indices.keys(), reverse=True)
dsu = DSU(n)
active = [False] * n
ans = 0
for v in distinct_vals:
idxs = val_to_indices[v]
for i in idxs:
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)
roots = set()
for i in idxs:
roots.add(dsu.find(i))
ans += len(roots)
return ans- Time: O(nα(n))
- Space: O(n)
