Make Array Non-decreasing - Practice Coding Problems

Make Array Non-decreasing - Problem

You are given an integer array nums. In one operation, you can select a subarray and replace it with a single element equal to its maximum value.

Return the maximum possible size of the array after performing zero or more operations such that the resulting array is non-decreasing.

A subarray is a contiguous sequence of elements within an array.

Input & Output

Example 1 — Basic Case

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

› Output: 1

💡 Note: We can replace the entire array [3,4,2,1] with its maximum value 4, resulting in [4] which is non-decreasing and has length 1.

Example 2 — Already Non-decreasing

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

› Output: 4

💡 Note: The array is already non-decreasing, so no operations are needed. The maximum length is 4.

Example 3 — Partial Replacement

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

› Output: 3

💡 Note: Replace subarray [3,2] with 3, resulting in [1,3,4] which is non-decreasing with length 3.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array with decreasing elements [3,4,2,1]

Replace

Replace entire array with maximum value 4

Output

Non-decreasing array [4] with length 1

Key Takeaway

🎯 Key Insight: Use a monotonic stack to greedily maintain the longest possible non-decreasing sequence

Asked in

G Google 35 a Amazon 28 M Microsoft 22 🍎 Apple 18

The key insight is to use a monotonic stack to maintain the longest possible non-decreasing sequence. When we encounter an element smaller than the stack top, we can merge the larger elements with it. Best approach uses greedy monotonic stack in O(n) time and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Monotonic Stack	O(n)	O(n)	Use a stack to maintain the longest possible non-decreasing sequence
Brute Force - Try All Combinations	O(2^n)	O(n)	Generate all possible ways to replace subarrays and check which gives maximum length

Greedy with Monotonic Stack — Algorithm Steps

Initialize empty stack
For each element, pop stack while top > current
Push current element to stack
Return stack size

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Elements

Go through array left to right

Pop Larger

Remove elements larger than current from stack

Push Current

Add current element to stack

Code -

solution.c — C

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

int solution(int* nums, int n) {
    int* stack = (int*)malloc(n * sizeof(int));
    int top = -1;
    
    for (int i = 0; i < n; i++) {
        // While stack top is greater than current number
        // we can merge them (replace with max which is stack top)
        while (top >= 0 && stack[top] > nums[i]) {
            top--;
        }
        
        // Add current number to stack
        stack[++top] = nums[i];
    }
    
    int result = top + 1;
    free(stack);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000], n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is pushed and popped at most once from the stack

✓ Linear Growth

Space Complexity

O(n)

Stack can store up to n elements in worst case

⚡ Linearithmic Space

32.4K Views

Medium Frequency

~25 min Avg. Time

890 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

Greedy with Monotonic Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler