Steps to Make Array Non-decreasing - Video Solutions

Problem Overview: You are given an integer array nums. In one step, remove every element nums[i] where nums[i] < nums[i-1]. The process repeats until the array becomes non‑decreasing. The goal is to compute how many steps this process takes.

Approach 1: Iterative Removal Simulation (O(n²) time, O(n) space)

This method directly simulates the rule described in the problem. Iterate through the array and mark elements where nums[i] < nums[i-1]. Build a new array that excludes those elements, then repeat the process until no more removals occur. Each iteration requires scanning the array and rebuilding it. In the worst case (for example, a strictly decreasing sequence), you remove only a few elements per round, which leads to up to n rounds and O(n²) total work. Space complexity is O(n) because you construct intermediate arrays. This approach is useful for understanding the mechanics of the problem but becomes slow for large inputs.

Approach 2: Monotonic Stack (O(n) time, O(n) space)

The optimized solution uses a stack to track elements and the number of steps before they disappear. Traverse the array from right to left. Maintain a decreasing monotonic stack that stores pairs of (value, stepsToRemove). When the current element is greater than the top of the stack, that means the smaller element will eventually be removed in a future round. Pop elements from the stack while they are smaller, and track the maximum steps required for those elements to disappear. Each pop represents a chain reaction of removals. The number of steps for the current element becomes maxSteps + 1. Push the result back onto the stack.

This works because every element can be pushed and popped at most once. The stack effectively compresses multiple removal rounds into a single pass. Instead of simulating each iteration, it calculates how long each element survives before being eliminated. The final answer is the maximum step value seen during processing. Time complexity is O(n) and space complexity is O(n). The technique is common in problems involving arrays and elimination chains, especially when using array traversal combined with monotonic structures.

Recommended for interviews: Interviewers typically expect the monotonic stack solution. The iterative simulation shows you understand the removal process but does not scale well. Implementing the stack approach demonstrates knowledge of elimination patterns, stack-based reasoning, and how to reduce repeated array passes into a linear-time algorithm.