Make Array Non-decreasing - Solution & Explanation

Problem Overview: You are given an integer array. In each round, remove every element nums[i] where nums[i] < nums[i-1]. Continue until the array becomes non-decreasing. The task is to compute how many rounds are required.

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

The most straightforward idea is to simulate the process exactly as described. Iterate through the array and remove elements that violate the non‑decreasing condition (nums[i] < nums[i-1]). After a pass, rebuild the array and repeat until no more removals happen. Each round scans the array and potentially shifts elements, which can cost O(n). In the worst case you perform up to O(n) rounds, leading to O(n²) time and O(n) auxiliary space for rebuilding the array. This approach is useful for understanding the mechanics but will time out for large inputs.

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

The key observation: an element disappears only because there is a larger value somewhere to its left that survives longer. Instead of simulating rounds, track how long each element takes before being removed. Use a decreasing monotonic stack that stores pairs of (value, stepsToDie). Traverse the array from left to right. While the stack top has a value ≤ current value, pop it and track the maximum removal time seen so far. If the stack becomes empty, the current element never gets removed. Otherwise it dies one round after the maximum popped delay. Push the element with its computed delay.

This greedy structure works because smaller elements to the left cannot protect the current element from a larger survivor further left. Each element is pushed and popped at most once, giving O(n) time and O(n) space. The approach relies heavily on patterns from stack processing and array traversal.

Approach 3: DP with Monotonic Stack Variant (O(n) time, O(n) space)

Another way to view the same idea is dynamic programming. Define dp[i] as the number of rounds before nums[i] gets removed. While iterating, pop stack elements smaller or equal to the current value and propagate the maximum dp value encountered. If a larger element remains on the stack, set dp[i] = maxDelay + 1. Otherwise dp[i] = 0. The global answer is the maximum dp[i]. This formulation clarifies why the stack approach works: each element inherits delay from blockers on its left.

Recommended for interviews: Interviewers expect the monotonic stack solution. The brute force simulation demonstrates understanding of the removal process, but the O(n) stack approach shows strong pattern recognition with greedy reasoning and stack-based array processing.