Steps to Make Array Non-decreasing - Practice Coding Problems

Steps to Make Array Non-decreasing - 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.

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

A non-decreasing array means each element is greater than or equal to the previous element: nums[i] >= nums[i-1].

Input & Output

Example 1 — Basic Case

$ Input: nums = [5,3,4,4,1]

› Output: 2

💡 Note: Step 1: Remove 3,4,1 (violations), left with [5,4]. Step 2: Remove 4, left with [5]. Total: 2 steps

Example 2 — Already Non-decreasing

$ Input: nums = [4,5,7,7,13]

› Output: 0

💡 Note: Array is already non-decreasing, no steps needed

Example 3 — Single Element

$ Input: nums = [1]

› Output: 0

💡 Note: Single element is always non-decreasing

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array with violations: [5,3,4,4,1]

Process

Remove violations where nums[i-1] > nums[i]

Output

Number of removal steps: 2

Key Takeaway

🎯 Key Insight: Use a monotonic stack to efficiently track how many removal rounds each element survives

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is that elements get removed in cascading waves, and we need to track how many rounds each element survives. The optimal approach uses a monotonic stack to efficiently compute survival rounds in O(n) time.

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack (Optimal)	O(n)	O(n)	Use stack to track how many rounds each element survives
Brute Force Simulation	O(n²)	O(n)	Simulate the removal process step by step until array becomes non-decreasing

Monotonic Stack (Optimal) — Algorithm Steps

Step 1: Process elements left to right with a monotonic decreasing stack
Step 2: For each element, pop smaller elements from stack and track max rounds
Step 3: Current element survives max_rounds + 1, push to stack

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Left to Right

Use stack to maintain decreasing order

Pop Smaller Elements

Current element removes smaller ones from stack

Track Max Rounds

Record maximum survival rounds

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int value;
    int rounds;
} Element;

int solution(int* nums, int size) {
    if (size <= 1) return 0;
    
    Element* stack = (Element*)malloc(size * sizeof(Element));
    int stackSize = 0;
    int maxSteps = 0;
    
    for (int i = 0; i < size; i++) {
        int num = nums[i];
        int rounds = 0;
        
        while (stackSize > 0 && stack[stackSize-1].value > num) {
            stackSize--;
            if (stack[stackSize].rounds > rounds) {
                rounds = stack[stackSize].rounds;
            }
        }
        
        if (rounds > 0) {
            rounds += 1;
        }
        
        if (rounds > maxSteps) {
            maxSteps = rounds;
        }
        
        stack[stackSize].value = num;
        stack[stackSize].rounds = rounds;
        stackSize++;
    }
    
    free(stack);
    return maxSteps;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is pushed and popped from stack at most once

✓ Linear Growth

Space Complexity

O(n)

Stack can contain up to n elements in worst case

⚡ Linearithmic Space

29.5K Views

Medium Frequency

~25 min Avg. Time

843 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler