Steps to Make Array Non-decreasing solution and explanation
7 more videos on this problem
Steps to Make Array Non-decreasing | Leetcode 2289 | Monotonic Stacks | Contest 295 🔥🔥Coding Decoded · 12:10 · 9K views
Weekly Contest 295 | 2289. Steps to Make Array Non-decreasingcodingMohan · 22:18 · 5K views
2289. Steps to Make Array Non-decreasing (Leetcode Medium)Programming Live with Larry · 48:15 · 2K views
【每日一题】LeetCode 2289. Steps to Make Array Non-decreasingHuifeng Guan · 1:11:42 · 1K views
Leetcode 2289. Steps to Make Array Non-decreasing - DP and monotonic stackCode-Yao · 15:02 · 649 views
Leetcode 2289DailyLeetcode · 12:14 · 463 views
Leetcode 2289. Steps to Make Array Non-decreasing (dp + monotonic stack)LetsCode · 15:41 · 453 views
LeetCode 2289 steps to make array non decreasing[CE] Code Engineering · 52:32 · 189 views
The 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 <= 1051 <= nums[i] <= 109
Approach overview
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.
Approach 1: Iterative Removal Approach
This approach involves iteratively removing all elements that violate the non-decreasing order condition. In each step, we go through the array, check for inversions, and build a new list excluding those elements. Each full iteration through the list counts as one step.
def steps_to_non_decreasing(nums):
steps = 0
while True:
changed = False
result = [nums[0]]
for i in range(1, len(nums)):
if nums[i - 1] <= nums[i]:
result.append(nums[i])
else:
changed = True
if not changed:
break
nums = result
steps += 1
return steps
# Test case
test_nums = [5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11]
print(steps_to_non_decreasing(test_nums))import java.util.ArrayList;
import java.util.List;
public class Main {
public static int stepsToNonDecreasing(int[] nums) {
int steps = 0;
while (true) {
boolean changed = false;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i == 0 || nums[i - 1] <= nums[i]) {
list.add(nums[i]);
} else {
changed = true;
}
}
if (!changed) break;
nums = list.stream().mapToInt(Integer::intValue).toArray();
steps++;
}
return steps;
}
public static void main(String[] args) {
int[] nums = {5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11};
System.out.println(stepsToNonDecreasing(nums));
}
}#include <vector>
#include <iostream>
using namespace std;
int stepsToNonDecreasing(vector<int>& nums) {
int steps = 0;
while (true) {
vector<int> temp;
bool changed = false;
for (int i = 0; i < nums.size(); ++i) {
if (i == 0 || nums[i-1] <= nums[i]) {
temp.push_back(nums[i]);
} else {
changed = true;
}
}
if (!changed) break;
nums = temp;
steps++;
}
return steps;
}
int main() {
vector<int> nums = {5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11};
cout << stepsToNonDecreasing(nums) << endl;
return 0;
}function stepsToNonDecreasing(nums) {
let steps = 0;
while (true) {
let changed = false;
let list = [];
for (let i = 0; i < nums.length; i++) {
if (i === 0 || nums[i - 1] <= nums[i]) {
list.push(nums[i]);
} else {
changed = true;
}
}
if (!changed) break;
nums = list;
steps++;
}
return steps;
}
let nums = [5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11];
console.log(stepsToNonDecreasing(nums));#include <stdio.h>
int stepsToNonDecreasing(int* nums, int numsSize) {
int steps = 0, i;
int currentSize;
while (1) {
int newIndex = 0;
int changed = 0;
for (i = 1; i < numsSize; i++) {
if (nums[i - 1] <= nums[i]) {
nums[newIndex++] = nums[i - 1];
} else {
changed = 1;
}
}
nums[newIndex++] = nums[numsSize - 1];
if (!changed) break;
numsSize = newIndex;
steps++;
}
return steps;
}
int main() {
int nums[] = {5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", stepsToNonDecreasing(nums, size));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int StepsToNonDecreasing(int[] nums) {
int steps = 0;
while (true) {
bool changed = false;
List<int> list = new List<int>();
list.Add(nums[0]);
for (int i = 1; i < nums.Length; i++) {
if (nums[i - 1] <= nums[i]) {
list.Add(nums[i]);
} else {
changed = true;
}
}
if (!changed) break;
nums = list.ToArray();
steps++;
}
return steps;
}
public static void Main() {
int[] nums = new int[] {5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11};
Solution solution = new Solution();
Console.WriteLine(solution.StepsToNonDecreasing(nums));
}
}Python's steps_to_non_decreasing function works through an iterative method where a new list with properly ordered elements is created as a copy of parts of nums. Iterations continue until no changes are necessary.
Time Complexity: O(n^2) due to iterative removals across the entire list.
Space Complexity: O(n) for the temporary list at each iteration.
Approach 2: Stack Approach
Instead of repeatedly removing elements, we simulate the process using a stack. The idea is to iterate through the array, and whenever we find an inversion, we simulate ‘removal’ by using the stack to maintain the largest non-decreasing subsequence seen so far.
def steps_to_non_decreasing(nums):
steps = 0
max_steps = 0
for i in range(1, len(nums)):
if nums[i - 1] > nums[i]:
steps += 1
else:
steps = 0
max_steps = max(max_steps, steps)
return max_steps
# Test case
test_nums = [5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11]
print(steps_to_non_decreasing(test_nums))public class Main {
public static int stepsToNonDecreasing(int[] nums) {
int steps = 0, maxSteps = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] > nums[i]) {
steps++;
} else {
steps = 0;
}
maxSteps = Math.max(maxSteps, steps);
}
return maxSteps;
}
public static void main(String[] args) {
int[] nums = {5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11};
System.out.println(stepsToNonDecreasing(nums));
}
}#include <vector>
#include <iostream>
int max(int a, int b) { return a > b ? a : b; }
int stepsToNonDecreasing(std::vector<int>& nums) {
int steps = 0;
int maxSteps = 0;
for (size_t i = 1; i < nums.size(); ++i) {
if (nums[i - 1] > nums[i]) {
steps++;
}
maxSteps = max(maxSteps, steps);
if (nums[i] >= nums[i - 1]) {
steps = 0;
}
}
return maxSteps;
}
int main() {
std::vector<int> nums = {5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11};
std::cout << stepsToNonDecreasing(nums) << std::endl;
return 0;
}function stepsToNonDecreasing(nums) {
let steps = 0;
let maxSteps = 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i - 1] > nums[i]) {
steps++;
} else {
steps = 0;
}
maxSteps = Math.max(maxSteps, steps);
}
return maxSteps;
}
let nums = [5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11];
console.log(stepsToNonDecreasing(nums));#include <stdio.h>
int max(int a, int b) { return a > b ? a : b; }
int stepsToNonDecreasing(int* nums, int numsSize) {
int steps = 0;
int ans = 0;
for (int i = 0; i < numsSize; i++) {
if (i > 0 && nums[i - 1] > nums[i])
steps++;
ans = max(ans, steps);
if (nums[i] >= nums[i-1])
steps = 0;
}
return ans;
}
int main() {
int nums[] = {5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", stepsToNonDecreasing(nums, size));
return 0;
}using System;
public class Solution {
public int StepsToNonDecreasing(int[] nums) {
int steps = 0, maxSteps = 0;
for (int i = 1; i < nums.Length; i++) {
if (nums[i - 1] > nums[i]) {
steps++;
} else {
steps = 0;
}
maxSteps = Math.Max(maxSteps, steps);
}
return maxSteps;
}
public static void Main() {
int[] nums = new int[] {5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11};
Solution solution = new Solution();
Console.WriteLine(solution.StepsToNonDecreasing(nums));
}
}Using Python, this function iterates through the numbers list, calculating continuously the number of change points wherein numbers aren’t naturally non-decreasing. On spotting these occurrence, it resets only when a valid transition is identified from a reduced number to an equal/higher one from its predecessor.
Time Complexity: O(n) for single-pass implementation.
Space Complexity: O(1) given fixed variable use.
Approach 3: Default Approach
function totalSteps(nums: number[]): number {
let ans = 0;
let stack = [];
for (let num of nums) {
let max = 0;
while (stack.length && stack[0][0] <= num) {
max = Math.max(stack[0][1], max);
stack.shift();
}
if (stack.length) max++;
ans = Math.max(max, ans);
stack.unshift([num, max]);
}
return ans;
}func totalSteps(nums []int) int {
stk := []int{}
ans, n := 0, len(nums)
dp := make([]int, n)
for i := n - 1; i >= 0; i-- {
for len(stk) > 0 && nums[i] > nums[stk[len(stk)-1]] {
dp[i] = max(dp[i]+1, dp[stk[len(stk)-1]])
stk = stk[:len(stk)-1]
ans = max(ans, dp[i])
}
stk = append(stk, i)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Removal Approach | Time Complexity: O(n^2) due to iterative removals across the entire list. |
| Stack Approach | Time Complexity: O(n) for single-pass implementation. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Removal Simulation | O(n²) | O(n) | Good for understanding the removal process or implementing a straightforward brute-force simulation. |
| Monotonic Stack | O(n) | O(n) | Best choice for interviews and large inputs. Converts repeated removal rounds into a single linear scan. |
Frequently asked questions
Is Steps to Make Array Non-decreasing easy or hard?
The problem is rated Medium on LeetCode but feels closer to Medium–Hard for many candidates. The brute-force idea is simple, but recognizing the monotonic stack pattern and computing removal rounds efficiently requires deeper algorithmic insight.
How to solve Steps to Make Array Non-decreasing in O(n)?
Use a monotonic decreasing stack while traversing the array from right to left. Store pairs of (value, steps). When the current element is larger than stack elements, pop them and track the maximum steps needed for their removal. The step count for the current element becomes maxSteps + 1. Track the global maximum as the final answer.
Steps to Make Array Non-decreasing Python or Java solution
In Python or Java, implement a stack storing pairs of value and step count. Iterate from right to left, pop smaller elements while tracking the maximum steps required, and push the current element with its computed step value. The maximum step encountered during the traversal is the answer.
What is the best approach for Steps to Make Array Non-decreasing?
The most efficient approach uses a monotonic stack. By scanning the array from right to left and tracking how many rounds each element survives, the algorithm determines the total steps in O(n) time and O(n) space. Each element is pushed and popped from the stack at most once, which guarantees linear performance.
What data structure is used in Steps to Make Array Non-decreasing?
The key data structure is a monotonic stack. It keeps elements in decreasing order and tracks how many rounds each element survives before removal. This structure helps efficiently simulate cascading deletions without repeatedly rebuilding the array.
What is the time complexity of Steps to Make Array Non-decreasing?
The optimal monotonic stack solution runs in O(n) time with O(n) space. A direct simulation that repeatedly removes invalid elements can take O(n²) time in the worst case because the array may need to be scanned and rebuilt many times.
Is Steps to Make Array Non-decreasing asked at Google, Amazon, or Meta?
This type of elimination-chain problem frequently appears in interviews at companies like Amazon, Google, and Meta. It tests understanding of monotonic stacks, array traversal patterns, and how to convert repeated operations into a linear-time algorithm.