Steps to Make Array Non-decreasing — Problem & Solution
Steps to Make Array Non-decreasing solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Steps to Make Array Non-decreasing is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Stack, Monotonic Stack
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums. In one step, every element nums[i] with nums[i - 1] > nums[i] is removed — all such elements at once, each judged against its left neighbour in the array as it was at the start of the step.
Steps repeat until the array is non-decreasing. Return how many steps are performed.
Example 1
Input: nums = [10,1,2,3,4,5]
Output: 5
Explanation: Each step removes only the element right after 10: first 1, then 2, then 3, 4 and 5.
Example 2
Input: nums = [6,2,5,1,7,3]
Output: 2
Explanation: Step 1 removes 2, 1 and 3, leaving [6,5,7]; step 2 removes 5, leaving [6,7].
Example 3
Input: nums = [3,3,4,9]
Output: 0
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^9
Hints for Steps to Make Array Non-decreasing
Hint 1
An element is eventually removed exactly when some earlier element is larger than it — but when is the question.
Hint 2
An element is eaten by the nearest earlier larger element, after everything between them that is smaller has been eaten first.
Hint 3
Scan left to right with a stack of (value, step it dies at). For a new value
x, pop entries with value<= xkeeping the largest death steptamong them; if the stack still has something,xdies att + 1, otherwise it never dies.
How to solve Steps to Make Array Non-decreasing
Each element that ever disappears is removed by its nearest earlier strictly larger element, and only after every element between them has been removed. So its removal step is one more than the latest removal step among the elements in between — a quantity a monotonic stack maintains.
Approach
- Keep a stack of pairs
(value, step)with values strictly decreasing from bottom to top;stepis when that element is removed (0 means never). - For each
xinnums, sett = 0and pop every pair whose value is<= x, takingt = max(t, step). - If the stack is now empty, nothing before
xis larger, soxsurvives: its step is 0. Otherwise its step ist + 1. - Push
(x, step)and track the maximum step seen — that is the answer.
Why it works
Let j be the nearest earlier element larger than x. Everything strictly between j and x is <= x, so none of it can eat x; x becomes adjacent to a larger element only once all of them are gone, which takes t steps, and it is eaten in the step after. The popped elements are exactly those between j and x that were still on the stack, and the ones popped earlier were removed no later than the ones that popped them, so the maximum is preserved. The process ends when the last removal happens, which is the largest step of all.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Simulating step by step is O(n²) on inputs like
[10,1,2,3,…]. - Pop on
<=: an equal element never eatsx, and it shields nothing from it either. - An element with no larger predecessor gets step 0 even if it popped entries with large steps.
Reference solution
Python
from typing import List
def totalSteps(nums: List[int]) -> int:
stack = [] # (value, step at which it is removed)
best = 0
for x in nums:
t = 0
while stack and stack[-1][0] <= x:
t = max(t, stack.pop()[1])
t = t + 1 if stack else 0
best = max(best, t)
stack.append((x, t))
return bestJava
public static int totalSteps(int[] nums) {
int n = nums.length;
int[] vals = new int[n], steps = new int[n];
int top = 0, best = 0;
for (int x : nums) {
int t = 0;
while (top > 0 && vals[top - 1] <= x) {
top--;
t = Math.max(t, steps[top]);
}
t = top > 0 ? t + 1 : 0;
best = Math.max(best, t);
vals[top] = x;
steps[top] = t;
top++;
}
return best;
}C++
int totalSteps(vector<int>& nums) {
vector<pair<int, int>> st;
int best = 0;
for (int x : nums) {
int t = 0;
while (!st.empty() && st.back().first <= x) {
t = max(t, st.back().second);
st.pop_back();
}
t = st.empty() ? 0 : t + 1;
best = max(best, t);
st.push_back(make_pair(x, t));
}
return best;
}JavaScript
var totalSteps = function(nums) {
var vals = [], steps = [];
var best = 0;
for (var i = 0; i < nums.length; i++) {
var x = nums[i], t = 0;
while (vals.length > 0 && vals[vals.length - 1] <= x) {
vals.pop();
t = Math.max(t, steps.pop());
}
t = vals.length > 0 ? t + 1 : 0;
if (t > best) best = t;
vals.push(x);
steps.push(t);
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure