Make Array Non-decreasing

Make Array Non-decreasing

What is this problem about?

In the Make Array Non-decreasing problem, you are given an integer array. In a single "step", you simultaneously remove every element arr[i] if it is strictly smaller than the element immediately to its left (arr[i-1]). This removal happens for all applicable elements at once. Your task is to determine how many steps it will take until the array becomes non-decreasing (i.e., sorted in ascending order), at which point no more elements will be removed.

Why is this asked in interviews?

This is an advanced problem that tests a candidate's mastery of the Monotonic Stack. Simulating the array deletion step-by-step requires $O(N^2)$ time in the worst case (like a reverse sorted array), leading to performance failures. Interviewers use this question to see if you can track "lifespans" or "rounds of deletion" for elements using a stack, showcasing deep algorithmic optimization skills.

Algorithmic pattern used

This problem relies on a Monotonic Stack that stores a tuple: (value, steps_to_be_deleted). We traverse the array backwards. For each element, it will "eat" (delete) all elements to its right that are strictly smaller than it. The number of steps this element takes to eat its smaller neighbors is max(current_steps + 1, neighbor_steps). We maintain a maximum steps variable globally, which becomes our final answer.

Example explanation

Array: [5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11] Let's look at a simpler segment: [5, 3, 4] Traversing backward:

• See 4. Stack: [(4, 0)].
• See 3. 3 cannot eat 4. Stack: [(4, 0), (3, 0)].
• See 5. 5 is larger than the top of stack (3). It eats 3. It takes 1 step. Steps for 5 is now 1. Stack: [(4, 0)].
• 5 is still larger than top of stack (4). It eats 4. But wait, did 4 take time to eat anything? No, it was 0. So 5 takes $1 + 1$ or just 2 steps to eat the 4? Since 4 didn't eat anything, 5 just eats it on the second step. The stack logic dynamically figures out the chain reactions of deletions without modifying arrays.

Common mistakes candidates make

Candidates frequently use a linked list to simulate the process, removing nodes and checking again. While better than an array, finding the nodes to delete still requires scanning, which degrades to $O(N^2)$ time. Another common error in the stack approach is calculating the steps incorrectly; an element doesn't just add +1 for every element it eats. It takes the max of its own current step count and the eaten element's step count.

Interview preparation tip

When dealing with the Make Array Non-decreasing interview pattern, study the "next greater element" stack template. Any problem where elements "eat", "block", or "delete" adjacent elements based on size comparisons almost always requires a Monotonic Stack. Practice storing secondary state (like 'survival time') alongside the values in the stack.