Problem Description

You have an integer array nums indexed from 0. The goal is to make this array non-decreasing (each element is less than or equal to the next one) through a specific removal process.

In each step, you simultaneously remove all elements nums[i] where the element immediately before it (nums[i-1]) is greater than nums[i]. This removal happens for all positions i from 1 to the end of the array in a single step.

After removing these elements, the remaining elements shift together to form a new array, and you repeat the process until no more removals are needed (the array becomes non-decreasing).

Your task is to count how many steps this process takes.

Example walkthrough:

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

• Step 1: Remove elements where previous element is greater - remove 3 (after 5), 3 (after 7), 8 (after 11), 5 (after 8)
• Continue this process until the array is non-decreasing
• Return the total number of steps needed

The solution uses a stack-based approach with dynamic programming. Working from right to left, it tracks for each position how many steps it would take for that element to be removed. The stack maintains indices of elements in increasing order of their values, and dp[i] stores the maximum steps needed if element i starts removing elements to its right.

Intuition

The key insight is to think about when each element will be removed rather than simulating the actual removal process step by step.

Consider any element nums[i]. It will only be removed if there's a larger element to its left that "survives" long enough to remove it. The question becomes: how many steps does it take for nums[i] to be removed?

Working backwards from right to left gives us an advantage: we can determine the "lifetime" of each element based on what happens to its right. For each position i, we need to know:

1. Which elements to the right will nums[i] directly remove (those smaller than nums[i])
2. How long those elements would have survived on their own

This leads to a critical observation: if nums[i] removes nums[j] directly (where j > i and nums[i] > nums[j]), then nums[i] must survive at least as long as it takes to remove nums[j], plus one more step for the actual removal.

Using a monotonic stack helps us efficiently track this relationship. As we traverse from right to left:

• When we find an element nums[i] that's larger than elements in our stack, it means nums[i] will remove those elements
• The removal time for nums[i] is the maximum of: one step to remove each direct neighbor, or the time needed for that neighbor to finish its own removals
• Elements that are never removed (those in increasing order) will have dp[i] = 0

The formula dp[i] = max(dp[i] + 1, dp[stk.pop()]) captures this: we either wait one more step than the previous removal, or we wait for the popped element to finish its cascade of removals, whichever takes longer.

The answer is the maximum value in the dp array, representing the longest chain of removals that will occur.

Learn more about Stack, Linked List and Monotonic Stack patterns.

Solution Approach

The solution uses a monotonic stack combined with dynamic programming to efficiently calculate the number of steps needed.

Data Structures:

• stk: A stack that maintains indices of elements in increasing order of their values
• dp: An array where dp[i] represents the number of steps until element at index i gets removed (0 if never removed)

Algorithm Steps:

1. Initialize structures:

   • Empty stack stk to store indices
   • Array dp of size n initialized with zeros
   • Variable ans to track the answer

2. Traverse from right to left (from index n-1 to 0):

   For each position i:

   a. Process elements that will be removed by nums[i]:

   while stk and nums[i] > nums[stk[-1]]:
       dp[i] = max(dp[i] + 1, dp[stk.pop()])

   • While the stack is not empty and current element is greater than the element at the top of stack
   • This means nums[i] will eventually remove nums[stk[-1]]
   • Update dp[i] to be the maximum of:
     • dp[i] + 1: One more step than previously calculated removals
     • dp[stk.pop()]: The steps needed for the popped element to complete its removals
   • This ensures we account for cascading removals

   b. Add current index to stack:

   stk.append(i)

   • After processing, add current index to maintain the monotonic property

3. Return the maximum value in dp:

   return max(dp)

   • The maximum value represents the longest chain of removals needed

Why this works:

• The stack maintains indices in increasing order of values when traversing right to left
• When we find an element that can remove others (stack elements with smaller values), we calculate how many steps it needs
• The max operation in the update ensures we wait for all cascading removals to complete
• Elements that are never removed remain with dp[i] = 0
• The final answer is the maximum steps any element needs, which represents when the array becomes non-decreasing

Time Complexity: O(n) - each element is pushed and popped from the stack at most once Space Complexity: O(n) - for the stack and dp array

Example Walkthrough

Let's trace through a small example: nums = [10, 6, 8, 7]

Initial Setup:

• stk = [] (empty stack)
• dp = [0, 0, 0, 0]
• We'll traverse from right to left (index 3 to 0)

Step 1: Process index 3 (value = 7)

• Stack is empty, no elements to remove
• Push index 3 to stack: stk = [3]
• dp = [0, 0, 0, 0]

Step 2: Process index 2 (value = 8)

• Check stack top: nums[2] = 8 > nums[3] = 7
• Element at index 2 will remove element at index 3
• Pop index 3: dp[2] = max(dp[2] + 1, dp[3]) = max(0 + 1, 0) = 1
• Push index 2 to stack: stk = [2]
• dp = [0, 0, 1, 0]

Step 3: Process index 1 (value = 6)

• Check stack top: nums[1] = 6 < nums[2] = 8
• No elements to remove (6 cannot remove 8)
• Push index 1 to stack: stk = [2, 1]
• dp = [0, 0, 1, 0]

Step 4: Process index 0 (value = 10)

• Check stack top: nums[0] = 10 > nums[1] = 6
• Pop index 1: dp[0] = max(dp[0] + 1, dp[1]) = max(0 + 1, 0) = 1
• Check stack top again: nums[0] = 10 > nums[2] = 8
• Pop index 2: dp[0] = max(dp[0] + 1, dp[2]) = max(1 + 1, 1) = 2
• Push index 0 to stack: stk = [0]
• dp = [2, 0, 1, 0]

Final Result: max(dp) = 2

What happens during actual removal:

• Step 1: Remove 6 (10 > 6), remove 7 (8 > 7) → Array becomes [10, 8]
• Step 2: Remove 8 (10 > 8) → Array becomes [10]
• Array is now non-decreasing after 2 steps ✓

The algorithm correctly identifies that element at index 0 (value 10) needs 2 steps to complete all its removals, which determines the total number of steps needed.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums.

The algorithm iterates through the array once from right to left (index n-1 to 0). For each element at index i, it performs stack operations:

• The while loop pops elements from the stack when nums[i] > nums[stk[-1]]
• Each element is pushed onto the stack exactly once and popped at most once

Since each element is pushed once and popped at most once throughout the entire execution, the total number of operations across all iterations is bounded by 2n. Therefore, despite the nested loop structure, the amortized time complexity is O(n).

Space Complexity: O(n) where n is the length of the input array.

The algorithm uses:

• A stack stk that can contain at most n elements (in the worst case, all indices are stored)
• A dynamic programming array dp of size n to store the number of steps for each position
• A few constant variables (ans, n, i)

The dominant space usage comes from the dp array and the stack, both of which can grow up to size n in the worst case, resulting in O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Understanding of Simultaneous Removal

Pitfall: A common mistake is thinking elements are removed one at a time sequentially, leading to incorrect step counting. For example, if nums = [10, 1, 2, 3, 4, 5], some might think:

• Step 1: Remove 1 (after 10) → [10, 2, 3, 4, 5]
• Step 2: Remove 2 (after 10) → [10, 3, 4, 5]
• And so on...

Reality: All qualifying elements are removed simultaneously in each step:

• Step 1: Remove 1, 2, 3, 4, 5 all at once → [10]
• Total: 1 step

Solution: Remember that in each step, ALL elements where nums[i-1] > nums[i] are removed together, not one by one.

2. Misunderstanding the DP Update Logic

Pitfall: Using dp[i] = dp[i] + 1 instead of dp[i] = max(dp[i] + 1, dp[stack.pop()]).

Consider nums = [7, 3, 5, 4]:

• When processing index 0 (value 7), it will remove index 1 (value 3)
• But value 3 needs to first remove value 4 (which takes 1 step)
• If we just use dp[i] + 1, we miss the cascading effect

Solution: The max operation ensures we wait for all cascading removals. If an element we're removing also removes other elements, we need to account for those steps.

3. Stack Order Confusion

Pitfall: Maintaining the wrong monotonic property in the stack. The stack should maintain indices where the corresponding values are in increasing order (when traversing right to left).

Wrong approach:

# Incorrect: trying to maintain decreasing order
while stack and nums[i] < nums[stack[-1]]:  # Wrong comparison
    dp[i] = max(dp[i] + 1, dp[stack.pop()])

Solution: Use the correct comparison nums[i] > nums[stack[-1]] to identify elements that will be removed by nums[i].

4. Edge Case: Already Non-Decreasing Array

Pitfall: Not handling arrays that are already non-decreasing, leading to unnecessary computations or incorrect results.

For nums = [1, 2, 3, 4, 5]:

• No removals are needed
• All dp[i] values remain 0
• Answer should be 0

Solution: The algorithm naturally handles this - when no element can remove others, all dp values stay 0, and max(dp) returns 0.

5. Traversal Direction Error

Pitfall: Traversing left to right instead of right to left.

Why right to left is crucial:

• We need to know what happens to elements on the right before processing elements on the left
• An element at position i affects elements at positions i+1, i+2, ...
• By processing right to left, we ensure all downstream effects are already calculated

Solution: Always traverse from n-1 to 0:

for i in range(n - 1, -1, -1):  # Correct direction