2289. Steps to Make Array Non-decreasing LeetCode Solution

In this guide, you will get 2289. Steps to Make Array Non-decreasing LeetCode Solution with the best time and space complexity. The solution to Steps to Make Array Non-decreasing problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Steps to Make Array Non-decreasing solution in C++
  4. Steps to Make Array Non-decreasing solution in Java
  5. Steps to Make Array Non-decreasing solution in Python
  6. Additional Resources
2289. Steps to Make Array Non-decreasing LeetCode Solution image

Problem Statement of 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

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

2289. Steps to Make Array Non-decreasing LeetCode Solution in C++

class Solution {
 public:
  int totalSteps(vector<int>& nums) {
    // dp[i] := the number of steps to remove nums[i]
    vector<int> dp(nums.size());
    stack<int> stack;

    for (int i = 0; i < nums.size(); ++i) {
      int step = 1;
      while (!stack.empty() && nums[stack.top()] <= nums[i])
        step = max(step, dp[stack.top()] + 1), stack.pop();
      if (!stack.empty())
        dp[i] = step;
      stack.push(i);
    }

    return ranges::max(dp);
  }
};
/* code provided by PROGIEZ */

2289. Steps to Make Array Non-decreasing LeetCode Solution in Java

class Solution {
  public int totalSteps(int[] nums) {
    // dp[i] := the number of steps to remove nums[i]
    int[] dp = new int[nums.length];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < nums.length; ++i) {
      int step = 1;
      while (!stack.isEmpty() && nums[stack.peek()] <= nums[i])
        step = Math.max(step, dp[stack.pop()] + 1);
      if (!stack.isEmpty())
        dp[i] = step;
      stack.push(i);
    }

    return Arrays.stream(dp).max().getAsInt();
  }
}
// code provided by PROGIEZ

2289. Steps to Make Array Non-decreasing LeetCode Solution in Python

class Solution:
  def totalSteps(self, nums: list[int]) -> int:
    # dp[i] := the number of steps to remove nums[i]
    dp = [0] * len(nums)
    stack = []

    for i, num in enumerate(nums):
      step = 1
      while stack and nums[stack[-1]] <= num:
        step = max(step, dp[stack.pop()] + 1)
      if stack:
        dp[i] = step
      stack.append(i)

    return max(dp)
# code by PROGIEZ

Additional Resources

See also  1707. Maximum XOR With an Element From Array LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.