Steps to Make Array Non-decreasing
Problem
Given a 0-indexed array nums, in one step remove every nums[i] for which nums[i − 1] > nums[i] (a strictly larger left neighbor). All such elements are removed simultaneously, the survivors close ranks, and we repeat. Return how many steps run until nums is non-decreasing.
nums = [5,3,4,4,7,3,6,11,8,5,11]3def totalSteps(nums):
# stack holds [value, rounds_until_removed], values strictly decreasing
stack = []
ans = 0
for v in nums:
cur = 0
# pop every element this v can "absorb" (it is >= them)
while stack and stack[-1][0] <= v:
cur = max(cur, stack.pop()[1])
# if something bigger is still to the left, v dies one round later
cur = cur + 1 if stack else 0
ans = max(ans, cur)
stack.append([v, cur])
return ansfunction totalSteps(nums) {
// stack holds [value, roundsUntilRemoved], values strictly decreasing
const stack = [];
let ans = 0;
for (const v of nums) {
let cur = 0;
// pop every element this v can "absorb" (it is >= them)
while (stack.length && stack[stack.length - 1][0] <= v) {
cur = Math.max(cur, stack.pop()[1]);
}
// if something bigger is still to the left, v dies one round later
cur = stack.length ? cur + 1 : 0;
ans = Math.max(ans, cur);
stack.push([v, cur]);
}
return ans;
}int totalSteps(int[] nums) {
// stack of {value, roundsUntilRemoved}, values strictly decreasing
Deque<int[]> stack = new ArrayDeque<>();
int ans = 0;
for (int v : nums) {
int cur = 0;
// pop every element this v can "absorb" (it is >= them)
while (!stack.isEmpty() && stack.peek()[0] <= v) {
cur = Math.max(cur, stack.pop()[1]);
}
// if something bigger is still to the left, v dies one round later
cur = stack.isEmpty() ? 0 : cur + 1;
ans = Math.max(ans, cur);
stack.push(new int[]{v, cur});
}
return ans;
}int totalSteps(vector<int>& nums) {
// stack of {value, roundsUntilRemoved}, values strictly decreasing
vector<pair<int,int>> stack;
int ans = 0;
for (int v : nums) {
int cur = 0;
// pop every element this v can "absorb" (it is >= them)
while (!stack.empty() && stack.back().first <= v) {
cur = max(cur, stack.back().second);
stack.pop_back();
}
// if something bigger is still to the left, v dies one round later
cur = stack.empty() ? 0 : cur + 1;
ans = max(ans, cur);
stack.push_back({v, cur});
}
return ans;
}Explanation
Simulating the rounds directly can cost O(n) rounds of O(n) work each — too slow for n up to 10⁵. The key observation: an element is removed iff some strictly greater element exists to its left in the original array. So instead of asking "what survives?", we ask, for each element, on which round does it die? The answer is the largest of those round numbers.
We sweep left to right keeping a monotonic stack of [value, round] pairs whose values strictly decrease from bottom to top. When the new value v arrives, every stacked element that is ≤ v would be deleted by v (or by whatever deletes those), so we pop them, taking the maximum of their death rounds into cur.
Why the max? All the popped elements sit between v and the next bigger element above it. v itself can only start being removed after every element it has to "chew through" is already gone — that bottleneck is the slowest neighbor, i.e. the maximum round among the popped ones. We then add 1 because v dies one round after that bottleneck clears, but only if a strictly greater element still remains to its left (the stack is non-empty). If the stack is empty, nothing bigger sits to the left, so v is never removed and its round is 0.
The global answer is the maximum death round seen. Each element is pushed and popped at most once, so the whole sweep is linear.
Worked example: [5,3,4,4,7,3,6,11,8,5,11]. The 3 after 5 dies in round 1; the trailing 8,5 get chewed by 11 across rounds, and the lone 4 in the middle survives longest, dying in round 3. The maximum, 3, is the answer.