Steps to Make Array Non-decreasing

Medium
1401.

Steps to Make Array Non-decreasing

Steps to Make Array Non-decreasing is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon, Google and Microsoft interviews.

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^5
  • 1 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var totalSteps = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 1 <= nums[i] <= 10^9

Hints for Steps to Make Array Non-decreasing

  1. Hint 1

    An element is eventually removed exactly when some earlier element is larger than it — but when is the question.

  2. Hint 2

    An element is eaten by the nearest earlier larger element, after everything between them that is smaller has been eaten first.

  3. Hint 3

    Scan left to right with a stack of (value, step it dies at). For a new value x, pop entries with value <= x keeping the largest death step t among them; if the stack still has something, x dies at t + 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

  1. Keep a stack of pairs (value, step) with values strictly decreasing from bottom to top; step is when that element is removed (0 means never).
  2. For each x in nums, set t = 0 and pop every pair whose value is <= x, taking t = max(t, step).
  3. If the stack is now empty, nothing before x is larger, so x survives: its step is 0. Otherwise its step is t + 1.
  4. 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 eats x, 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 best

Java

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