# Steps to Make Array Non-decreasing
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/steps-to-make-array-non-decreasing)
Canonical: https://scaleengineer.com/dsa/problems/steps-to-make-array-non-decreasing
**Data structures:** Array, Linked List, Stack, Monotonic Stack
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley)
---
## Problem
You are given a **0-indexed** integer array `nums`. In one step, **remove** all elements `nums[i]` where `nums[i - 1] > nums[i]` for all `0 < i < nums.length`.

Return _the number of steps performed until_ `nums` _becomes a **non-decreasing** array_.

**Example 1:**

**Input:** nums = [5,3,4,4,7,3,6,11,8,5,11]
**Output:** 3
**Explanation:** The following are the steps performed:
- Step 1: [5,**3**,4,4,7,**3**,6,11,**8**,**5**,11] becomes [5,4,4,7,6,11,11]
- Step 2: [5,**4**,4,7,**6**,11,11] becomes [5,4,7,11,11]
- Step 3: [5,**4**,7,11,11] becomes [5,7,11,11]
[5,7,11,11] is a non-decreasing array. Therefore, we return 3.

**Example 2:**

**Input:** nums = [4,5,7,7,13]
**Output:** 0
**Explanation:** nums is already a non-decreasing array. Therefore, we return 0.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. We repeatedly scan the array, identify all elements that are smaller than their preceding element, and remove them. We count how many such removal steps are needed until the array becomes non-decreasing.
**Time:** O(N^2), where N is the initial number of elements. In the worst-case scenario (e.g., a strictly decreasing array), we might perform O(N) steps. Each step involves iterating through the current array to find elements to remove and then building a new array, which takes O(K) time where K is the current array size. This leads to a total time complexity of roughly N + (N-1) + (N-2) + ... + 1, which is O(N^2). · **Space:** O(N), where N is the initial number of elements in the array. In each step, we need extra space to store the indices to be removed and to build the array for the next step. The maximum size of these lists is proportional to N.
**Pros:** It's straightforward to understand as it directly translates the problem statement into code.; The logic is simple to implement without requiring complex data structures or algorithms.
**Cons:** The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.; Creating a new list in every step can be memory-intensive, although the total space remains O(N).
### Explanation
The core idea is to mimic the step-by-step removal process. We use a loop that continues as long as the array is not sorted. In each iteration of the loop, which represents one step, we first identify all elements `nums[i]` such that `nums[i-1] > nums[i]`. We store their indices. If no such elements are found, the array is non-decreasing, and we can stop. Otherwise, we increment our step counter and construct the array for the next step by removing all the identified elements. Using a dynamic data structure like an `ArrayList` in Java simplifies the removal and resizing of the array in each step.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int totalSteps(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        List<Integer> currentNums = new ArrayList<>();
        for (int num : nums) {
            currentNums.add(num);
        }

        int steps = 0;
        while (true) {
            List<Integer> toRemoveIndices = new ArrayList<>();
            for (int i = 1; i < currentNums.size(); i++) {
                if (currentNums.get(i - 1) > currentNums.get(i)) {
                    toRemoveIndices.add(i);
                }
            }

            if (toRemoveIndices.isEmpty()) {
                break;
            }

            steps++;
            List<Integer> nextNums = new ArrayList<>();
            int removeIndexPtr = 0;
            for (int i = 0; i < currentNums.size(); i++) {
                if (removeIndexPtr < toRemoveIndices.size() && toRemoveIndices.get(removeIndexPtr) == i) {
                    removeIndexPtr++;
                } else {
                    nextNums.add(currentNums.get(i));
                }
            }
            currentNums = nextNums;
        }

        return steps;
    }
}
```
### Algorithm
- Initialize a variable `steps` to 0.
- Start an infinite loop to simulate the steps.
- Inside the loop, create a list to store the indices of elements that need to be removed in the current step. Iterate through the current array from the second element (`i=1`) to the end. If `nums[i-1] > nums[i]`, add index `i` to the removal list.
- If the removal list is empty, it means the array is non-decreasing. Break the loop.
- If the list is not empty, increment `steps`.
- Create a new array (or list) by filtering out the elements at the indices marked for removal.
- Replace the old array with this new one.
- After the loop terminates, return `steps`.

## Monotonic Stack and Dynamic Programming
A more efficient approach uses dynamic programming combined with a monotonic stack. The key idea is to determine, for each element `nums[i]`, how many steps it takes for it to be removed. The final answer is the maximum of these values. A monotonic stack helps us efficiently find the preceding element that will cause the removal and calculate the time it takes by considering the elements that need to be removed in between.
**Time:** O(N), where N is the number of elements in the array. Each element's index is pushed onto the stack exactly once and popped at most once. All operations within the loop are amortized constant time. · **Space:** O(N), where N is the number of elements. This is for the `dp` array and the stack. In the worst case (a strictly decreasing array), the stack can hold up to N elements.
**Pros:** Optimal time complexity of O(N), making it very efficient for large inputs.; Solves the problem in a single pass through the array.
**Cons:** The logic is more complex and less intuitive compared to the direct simulation.; Requires careful handling of the stack and the `dp` array logic to ensure correctness.
### Explanation
Let `dp[i]` be the number of steps required to remove `nums[i]`. If `nums[i]` is never removed, `dp[i] = 0`. The answer to the problem is `max(dp)`. We can compute `dp` for all `i` in a single pass from left to right.

An element `nums[i]` is removed when its left neighbor becomes larger than it. This can happen in step 1 if `nums[i-1] > nums[i]`, or in a later step if `nums[i-1]` (and potentially other elements) are removed, exposing `nums[i]` to a new, larger neighbor from further left.

The number of steps to remove `nums[i]` is `1 +` the number of steps required to remove all the 'blocking' elements between `nums[i]` and the first element to its left that is larger than it.

A monotonic stack (specifically, one that maintains indices of elements in decreasing order of value) is perfect for this. As we iterate through `nums` with index `i`, the stack helps us keep track of the chain of potential 'removers' to the left of `i`.

When considering `nums[i]`, we pop elements `nums[j]` from the stack if `nums[j] <= nums[i]`. For each popped element `j`, we know it takes `dp[j]` steps to be removed. We need to wait for the slowest of these removals. We keep track of the maximum `dp` value among all popped elements. After popping, if the stack is not empty, its top element `nums[k]` is the first element to the left of `i` that is greater than `nums[i]`. `nums[i]` will be removed by `nums[k]` one step after all the intermediate elements are gone. This gives us `dp[i]`. If the stack becomes empty, `nums[i]` is larger than or equal to all elements to its left and will never be removed.

```java
import java.util.Stack;

class Solution {
    public int totalSteps(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Stack<Integer> stack = new Stack<>();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            int currentSteps = 0;
            // Pop elements from the stack that are smaller or equal to the current element.
            // These elements are 'eaten' by the current element or a previous larger one.
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                // The current element nums[i] has to wait for the element at stack.peek()
                // to be removed. We take the maximum of the steps needed for all such elements.
                currentSteps = Math.max(currentSteps, dp[stack.pop()]);
            }

            if (!stack.isEmpty()) {
                // The element at stack.peek() is greater than nums[i].
                // It will remove nums[i]. This happens one step after all elements
                // between them are removed.
                dp[i] = currentSteps + 1;
            } else {
                // If stack is empty, no element to the left is greater than nums[i].
                // So, nums[i] will never be removed.
                dp[i] = 0;
            }

            // Update the maximum steps seen so far.
            ans = Math.max(ans, dp[i]);
            // Push the current index onto the stack.
            stack.push(i);
        }

        return ans;
    }
}
```
### Algorithm
- Initialize a `dp` array of size `n` to store the removal steps for each element, and an integer `ans` to 0 to track the maximum steps.
- Use a stack to store indices of elements that form a monotonically decreasing sequence.
- Iterate through the `nums` array from left to right with index `i`:
  - Initialize `current_steps = 0`.
  - While the stack is not empty and the element at the top of the stack is less than or equal to the current element `nums[i]`, it means the element at `stack.peek()` is 'shielded' by `nums[i]`. We must wait for it to be removed. The time it takes is `dp[stack.peek()]`. We update `current_steps = max(current_steps, dp[stack.peek()])` and pop from the stack.
  - After the loop, if the stack is empty, it means no element to the left is larger than `nums[i]`, so `nums[i]` will never be removed. `dp[i]` remains 0.
  - If the stack is not empty, the element at `stack.peek()` is larger than `nums[i]` and will be its eventual remover. The removal will happen one step after all intermediate elements (which we just popped) are removed. So, `dp[i] = current_steps + 1`.
  - Update the overall answer: `ans = max(ans, dp[i])`.
  - Push the current index `i` onto the stack.
- Return `ans`.

# Solutions
### Java

```java
class Solution {
public
  int totalSteps(int[] nums) {
    Deque<Integer> stk = new ArrayDeque<>();
    int ans = 0;
    int n = nums.length;
    int[] dp = new int[n];
    for (int i = n - 1; i >= 0; --i) {
      while (!stk.isEmpty() && nums[i] > nums[stk.peek()]) {
        dp[i] = Math.max(dp[i] + 1, dp[stk.pop()]);
        ans = Math.max(ans, dp[i]);
      }
      stk.push(i);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int totalSteps(vector<int> &nums) {
    stack<int> stk;
    int ans = 0, n = nums.size();
    vector<int> dp(n);
    for (int i = n - 1; i >= 0; --i) {
      while (!stk.empty() && nums[i] > nums[stk.top()]) {
        dp[i] = max(dp[i] + 1, dp[stk.top()]);
        ans = max(ans, dp[i]);
        stk.pop();
      }
      stk.push(i);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def totalSteps(self, nums: List[int]) -> int: stk = [] ans, n = 0, len(nums) dp = [0] * n for i in range(n - 1, - 1, - 1): while stk and nums[i] > nums[stk[- 1]]: dp[i] = max(dp[i] + 1, dp[stk . pop()]) stk . append(i) return max(dp)

```