{x}
blog image

Steps to Make Array Non-decreasing

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.

Return the number of steps performed until nums becomes a non-decreasing array.

 

Example 1:

Input: nums = [5,3,4,4,7,3,6,11,8,5,11]
Output: 3
Explanation: 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
Explanation: nums is already a non-decreasing array. Therefore, we return 0.

 

Constraints:

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

Solution Explanation for Steps to Make Array Non-decreasing

This problem asks to find the number of steps required to make an array non-decreasing. In each step, we remove all elements nums[i] where nums[i-1] > nums[i] for all 0 < i < nums.length. The solution uses a monotonic stack approach with dynamic programming to efficiently track the steps.

Approach:

The core idea is to iterate through the array from right to left. For each element, we check if it's smaller than the element to its right. If it is, we can potentially remove it in a step. To efficiently determine the number of steps needed for each element, we maintain a stack and a dp array.

  • Monotonic Stack: The stack stk stores indices of elements. It's maintained such that the elements at the indices in the stack are in non-decreasing order (from top to bottom).

  • Dynamic Programming (dp array): dp[i] stores the maximum number of steps that can be performed considering elements up to and including index i.

Algorithm:

  1. Initialization: Initialize an empty stack stk and a dp array filled with zeros.

  2. Iteration: Iterate through the nums array from right to left (index i from n-1 down to 0).

  3. Stack Processing: For each element nums[i], we pop elements from the stack as long as:

    • The stack is not empty, and
    • nums[i] > nums[stk.top()] (meaning nums[i] is greater than the element at the top of the stack).

    For each popped element stk.top(), we update dp[i] using dynamic programming: dp[i] = max(dp[i] + 1, dp[stk.top()]) This accounts for the additional step gained by removing the popped element and considers the maximum steps achievable from previously processed elements.

  4. Stack Push: After processing the stack, push the current index i onto the stack.

  5. Result: After iterating through the entire array, the maximum value in the dp array represents the total number of steps needed to make the array non-decreasing.

Time Complexity Analysis:

The algorithm iterates through the array once. The stack operations (push and pop) take amortized O(1) time each. Therefore, the overall time complexity is O(n), where n is the length of the input array.

Space Complexity Analysis:

The space complexity is determined by the stack and the dp array. Both have a maximum size of n. Therefore, the space complexity is O(n).

Code Explanation (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)

The code directly implements the algorithm described above. The max(dp) function at the end finds the maximum value in the dp array, giving us the total number of steps. The other language versions follow the same logic.

This solution efficiently solves the problem using a combination of monotonic stack and dynamic programming, achieving a linear time and space complexity.