#2289

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Steps to Make Array Non-decreasing

Determine the minimum steps to make an array non-decreasing using linked-list pointer manipulation and monotonic stack techniques efficiently.

array linked list stack monotonic stack

Problem Statement

Given a 0-indexed integer array nums, repeatedly perform the following operation: remove all nums[i] where nums[i - 1] > nums[i] for all 0 < i < nums.length. Return the total number of steps until nums becomes non-decreasing.

Example 1: Input: nums = [5,3,4,4,7,3,6,11,8,5,11]; Output: 3. Explanation: Step 1 removes elements violating the non-decreasing order, resulting in [5,4,4,7,6,11,11]. Step 2 yields [5,4,7,11,11], and Step 3 produces [5,7,11,11], which is non-decreasing.

Examples

Example 1

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

Output: 3

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

nums is already a non-decreasing array. Therefore, we return 0.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109

Solution Approach

Simulate Removal with Iteration

Loop through the array repeatedly, removing elements where nums[i-1] > nums[i]. Count each full pass as a step until no elements are removed. This brute-force method illustrates the pattern of left-to-right violation detection but may time out for large arrays.

Linked-List Pointer Optimization

Transform the array into a linked list to track neighbors efficiently. Remove nodes directly when left neighbor is greater. This reduces redundant scans, leveraging pointer manipulation to quickly implement the exact step-removal logic.

Monotonic Stack Approach

Use a stack to maintain non-decreasing elements. For each new element, pop from the stack until the stack top is less than or equal to the current element. Count the levels of removals as steps, connecting stack depth to the total step count.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(n) for optimized monotonic stack or linked-list pointer approaches to O(n^2) for naive iteration. Space complexity is O(n) for stack or linked-list representations.

What Interviewers Usually Probe

Look for an efficient way to detect elements violating non-decreasing order without full array scans.
Expect the candidate to connect array behavior to linked-list pointer updates or stack levels.
Notice if candidate handles edge cases like already non-decreasing arrays or single-element arrays.

Common Pitfalls or Variants

Common pitfalls

Removing elements directly from the array without considering index shifts can lead to wrong results.
Failing to count steps correctly when multiple elements are removed in one pass.
Ignoring the need for repeated passes until the array stabilizes as non-decreasing.

Follow-up variants

Instead of deleting elements, return the minimum number of increment operations needed to achieve non-decreasing order.
Apply the same removal rules but on a circular array where the last element compares to the first.
Track positions of removed elements per step to optimize subsequent operations for large arrays.

FAQ

What is the main idea behind the Steps to Make Array Non-decreasing problem?

The goal is to remove elements that break the non-decreasing order repeatedly until the array stabilizes, counting the steps needed.

Can this problem be solved without simulating every removal?

Yes, using a linked-list or monotonic stack allows tracking violations efficiently, avoiding full array rescans each step.

How does linked-list pointer manipulation help in this problem?

It allows direct removal of elements and quick neighbor access, mirroring the step-wise deletion process efficiently.

What is the time complexity of the optimal solution?

Using a monotonic stack or linked-list pointers, the time complexity is O(n) with O(n) space for auxiliary structures.

What happens if the array is already non-decreasing?

No elements are removed, so the number of steps returned is 0, which the simulation or stack-based approach handles naturally.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        stk = []
        ans, n = 0, len(nums)
        dp = [0] * n
        for i in range(n - 1, -1, -1):
            while stk and nums[i] > nums[stk[-1]]:
                dp[i] = max(dp[i] + 1, dp[stk.pop()])
            stk.append(i)
        return max(dp)

Continue Practicing

#2281 sum of total strength of wizards #2334 subarray with elements greater than varying threshold #2454 next greater element iv