Scale Engineer

Steps to Make Array Non-decreasing

Med
#2087Time: O(N^2), where N is the initial number of elements. In the worst-case scenario (e.g., a strictly decreasing array), we might perform O(N) steps. Each step involves iterating through the current array to find elements to remove and then building a new array, which takes O(K) time where K is the current array size. This leads to a total time complexity of roughly N + (N-1) + (N-2) + ... + 1, which is O(N^2).Space: O(N), where N is the initial number of elements in the array. In each step, we need extra space to store the indices to be removed and to build the array for the next step. The maximum size of these lists is proportional to N.1 company
Data structures
ArrayLinked ListStackMonotonic Stack
Companies
Morgan Stanley

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We repeatedly scan the array, identify all elements that are smaller than their preceding element, and remove them. We count how many such removal steps are needed until the array becomes non-decreasing.

Algorithm

  • Initialize a variable steps to 0.
  • Start an infinite loop to simulate the steps.
  • Inside the loop, create a list to store the indices of elements that need to be removed in the current step. Iterate through the current array from the second element (i=1) to the end. If nums[i-1] > nums[i], add index i to the removal list.
  • If the removal list is empty, it means the array is non-decreasing. Break the loop.
  • If the list is not empty, increment steps.
  • Create a new array (or list) by filtering out the elements at the indices marked for removal.
  • Replace the old array with this new one.
  • After the loop terminates, return steps.

Walkthrough

The core idea is to mimic the step-by-step removal process. We use a loop that continues as long as the array is not sorted. In each iteration of the loop, which represents one step, we first identify all elements nums[i] such that nums[i-1] > nums[i]. We store their indices. If no such elements are found, the array is non-decreasing, and we can stop. Otherwise, we increment our step counter and construct the array for the next step by removing all the identified elements. Using a dynamic data structure like an ArrayList in Java simplifies the removal and resizing of the array in each step.

import java.util.ArrayList;import java.util.List; class Solution {    public int totalSteps(int[] nums) {        int n = nums.length;        if (n <= 1) {            return 0;        }         List<Integer> currentNums = new ArrayList<>();        for (int num : nums) {            currentNums.add(num);        }         int steps = 0;        while (true) {            List<Integer> toRemoveIndices = new ArrayList<>();            for (int i = 1; i < currentNums.size(); i++) {                if (currentNums.get(i - 1) > currentNums.get(i)) {                    toRemoveIndices.add(i);                }            }             if (toRemoveIndices.isEmpty()) {                break;            }             steps++;            List<Integer> nextNums = new ArrayList<>();            int removeIndexPtr = 0;            for (int i = 0; i < currentNums.size(); i++) {                if (removeIndexPtr < toRemoveIndices.size() && toRemoveIndices.get(removeIndexPtr) == i) {                    removeIndexPtr++;                } else {                    nextNums.add(currentNums.get(i));                }            }            currentNums = nextNums;        }         return steps;    }}

Complexity

Time

O(N^2), where N is the initial number of elements. In the worst-case scenario (e.g., a strictly decreasing array), we might perform O(N) steps. Each step involves iterating through the current array to find elements to remove and then building a new array, which takes O(K) time where K is the current array size. This leads to a total time complexity of roughly N + (N-1) + (N-2) + ... + 1, which is O(N^2).

Space

O(N), where N is the initial number of elements in the array. In each step, we need extra space to store the indices to be removed and to build the array for the next step. The maximum size of these lists is proportional to N.

Trade-offs

Pros

  • It's straightforward to understand as it directly translates the problem statement into code.

  • The logic is simple to implement without requiring complex data structures or algorithms.

Cons

  • The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.

  • Creating a new list in every step can be memory-intensive, although the total space remains O(N).

Solutions

class Solution {public  int totalSteps(int[] nums) {    Deque<Integer> stk = new ArrayDeque<>();    int ans = 0;    int n = nums.length;    int[] dp = new int[n];    for (int i = n - 1; i >= 0; --i) {      while (!stk.isEmpty() && nums[i] > nums[stk.peek()]) {        dp[i] = Math.max(dp[i] + 1, dp[stk.pop()]);        ans = Math.max(ans, dp[i]);      }      stk.push(i);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem