LeetCode 2289 - Steps to Make Array Non-decreasing

Difficulty: 🟡 Medium
Topics: Array, Linked List, Dynamic Programming, Stack, Monotonic Stack, Simulation

Solution

Problem Understanding

The problem asks us to determine how many steps it takes to make a given array nums non-decreasing by repeatedly removing elements that break the non-decreasing property. Specifically, for each step, any element nums[i] where nums[i - 1] > nums[i] is removed. This process continues until the array is entirely non-decreasing. The input is a 0-indexed array of integers, and the output is a single integer representing the number of steps required.

The constraints indicate that the array can be large, up to 10^5 elements, and each element can be up to 10^9. This suggests that a naive approach that repeatedly scans and removes elements directly from the array could be too slow. Important edge cases include arrays that are already non-decreasing, arrays that are strictly decreasing, arrays with duplicate elements, and arrays with only one element.

Approaches

The brute-force approach involves simulating the process as described in the problem statement. In each iteration, we scan the array from left to right, identify all elements where nums[i - 1] > nums[i], remove them, and repeat until no elements need removal. While this is correct, it can take up to O(n^2) time in the worst case because each step may remove only one element, and scanning the array repeatedly is expensive.

The optimal approach relies on the observation that the number of steps needed to remove an element depends on the elements to its left. Using a monotonic stack, we can track decreasing sequences and determine for each element the number of steps until it is removed. For each element, we check the elements in the stack and compute its step count as one more than the maximum step count of elements that are larger than it. This allows computing the total steps in a single pass.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Simulate each step explicitly, removing violating elements iteratively
Optimal	O(n)	O(n)	Use a monotonic stack to track the number of steps for each element efficiently

Algorithm Walkthrough

Initialize an empty stack. Each stack element will be a pair (value, steps) where value is the element from nums and steps is the number of steps until it would be removed.
Initialize a variable max_steps to 0. This will track the maximum number of steps among all elements.
Iterate over each element num in nums:
Initialize a local counter steps to 0.
While the stack is non-empty and the top element of the stack has a value less than or equal to num, pop it and update steps to the maximum of steps and the popped element's steps.
If the stack is non-empty after this, increment steps by 1 since num will eventually be removed due to the larger element on the left.
Push (num, steps) onto the stack.
Update max_steps to the maximum of max_steps and steps.
After processing all elements, return max_steps.

Why it works: The stack maintains a decreasing sequence of elements from left to right. By storing the number of steps each element takes to be removed, we can compute the step count for each new element in O(1) amortized time per element. This guarantees that the maximum step count calculated corresponds to the total number of iterations needed to make the array non-decreasing.

Python Solution

from typing import List

class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        stack = []  # Stack of pairs (value, steps)
        max_steps = 0
        
        for num in nums:
            steps = 0
            while stack and stack[-1][0] <= num:
                steps = max(steps, stack.pop()[1])
            if stack:
                steps += 1
            stack.append((num, steps))
            max_steps = max(max_steps, steps)
        
        return max_steps

In this Python solution, the stack is used to store tuples of (value, steps). For each number, we determine how many steps it will take to be removed by checking previous elements that are smaller or equal. If there is still a larger element left in the stack, we increment the step count. max_steps keeps track of the overall steps needed.

Go Solution

func totalSteps(nums []int) int {
	type pair struct {
		val, steps int
	}
	stack := []pair{}
	maxSteps := 0

	for _, num := range nums {
		steps := 0
		for len(stack) > 0 && stack[len(stack)-1].val <= num {
			steps = max(steps, stack[len(stack)-1].steps)
			stack = stack[:len(stack)-1]
		}
		if len(stack) > 0 {
			steps++
		}
		stack = append(stack, pair{num, steps})
		if steps > maxSteps {
			maxSteps = steps
		}
	}

	return maxSteps
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

In Go, the same monotonic stack approach is used. We define a pair struct to hold both the value and the step count. Slice operations are used to simulate stack push and pop operations. The logic mirrors the Python implementation closely.

Worked Examples

Example 1: nums = [5,3,4,4,7,3,6,11,8,5,11]

Element	Stack Before	Popped Elements	Steps	Stack After
5	[]	None	0	[(5,0)]
3	[(5,0)]	None	1	[(5,0),(3,1)]
4	[(5,0),(3,1)]	(3,1)	1	[(5,0),(4,1)]
4	[(5,0),(4,1)]	(4,1)	1	[(5,0),(4,1),(4,1)]
7	[(5,0),(4,1),(4,1)]	(4,1),(4,1),(5,0)	1	[(7,1)]
3	[(7,1)]	None	1	[(7,1),(3,1)]
6	[(7,1),(3,1)]	(3,1)	1	[(7,1),(6,1)]
11	[(7,1),(6,1)]	(6,1),(7,1)	1	[(11,1)]
8	[(11,1)]	None	2	[(11,1),(8,2)]
5	[(11,1),(8,2)]	None	3	[(11,1),(8,2),(5,3)]
11	[(11,1),(8,2),(5,3)]	(5,3),(8,2),(11,1)	0	[(11,0)]

Maximum steps = 3

Example 2: nums = [4,5,7,7,13]

No elements are removed, so max_steps = 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is pushed and popped at most once from the stack
Space	O(n)	The stack can contain up to n elements in the worst case

The time complexity is linear because every element is examined only once, and stack operations are amortized O(1). The space complexity is proportional to the stack size.

Test Cases

# Provided examples
assert Solution().totalSteps([5,3,4,4,7,3,6,11,8,5,11]) == 3  # example 1
assert Solution().totalSteps([4,5,7,7,13]) == 0               # example 2

# Edge cases
assert Solution().totalSteps([1]) == 0                        # single element
assert Solution().totalSteps([5,4,3,2,1]) == 4               # strictly decreasing
assert Solution().totalSteps([1,2,3,4,5]) == 0               # strictly increasing
assert Solution().totalSteps([2,2,2,2,2]) == 0               # all equal elements
assert Solution().totalSteps([1,3,2,4,3,5]) == 2             # alternating increase/decrease

Test	Why
[5,3,4,4,7,3,6,11,8,5,11]	General case with multiple removals
[4,5,7,7,13]	Already non-decreasing
[1]	Minimal input
[5,4,3,2,1]	Strictly decreasing array
[1,2,3,4,5]	Strictly increasing array
[2,2,2,