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.
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
