How hard is LeetCode 2289. Steps to Make Array Non-decreasing?

LeetCode 2289. Steps to Make Array Non-decreasing is rated Medium on LeetCode.

What is the time complexity of LeetCode 2289. Steps to Make Array Non-decreasing?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 2289. Steps to Make Array Non-decreasing?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 2289. Steps to Make Array Non-decreasing cover?

LeetCode 2289. Steps to Make Array Non-decreasing is tagged Stack, Array, Linked List and Monotonic Stack on LeetCode.

Steps to Make Array Non-decreasing — LeetCode 2289 Python Solution

MediumStackArrayLinked ListMonotonic Stack

Problem: #2289
Pattern: Linked List
Reading time: 2 min
Source: leetcode.com

The problem

You are given a 0-indexed integer array nums. In one step, remove all elements nums[i] where nums[i - 1] > nums[i] for all 0 < i < nums.length.

Example

Input: nums = [5,3,4,4,7,3,6,11,8,5,11]
Output: 3
Explanation: The following are the steps performed:

Python solution

Python

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)

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 2289. Steps to Make Array Non-decreasing is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2289. Steps to Make Array Non-decreasing?: LeetCode 2289. Steps to Make Array Non-decreasing is rated Medium on LeetCode.
What is the time complexity of LeetCode 2289. Steps to Make Array Non-decreasing?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 2289. Steps to Make Array Non-decreasing?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2289. Steps to Make Array Non-decreasing cover?: LeetCode 2289. Steps to Make Array Non-decreasing is tagged Stack, Array, Linked List and Monotonic Stack on LeetCode.