# Monotonic Stack > A stack that keeps its values in order lets every element find its next smaller (or larger) neighbour in one pass. How it works, why it is O(n), and where it shows up. - Track: DSA (Concepts) - Level: Intermediate - Format: Step-through player - Author: Aayush Ostwal - Published: 27 October 2026 - Topics: Monotonic stack, Stack, Data structure - Canonical URL: https://compoundengineer.com/library/dsa/monotonic-stack Concept · Stacks Intermediate · O(n) time · O(n) space ## Why it exists Imagine a row of people standing in a line, each with a height. Every person wants to know: who is the first person to my right who is shorter than me? That is the "next smaller" question, and it comes up all over array problems: stock spans, rainfall, histograms, "days until a warmer day". The direct way is for each person to look to the right until they see someone shorter. When the line only goes up, such as [1, 2, 3, …, n] , nobody ever finds anyone, so every person looks at everyone to their right. That is about n²/2 looks. For n = 10⁵ it is 5 × 10⁹. Notice the waste. When person 1 looks past persons 2, 3 and 4, those people are about to look at exactly the same persons again. Can the people who are still waiting share one look at the line instead of each walking alone? ## The core idea Walk the line once, left to right, and keep a pile of the people who are still waiting for a shorter person. You only touch the top of the pile, like a stack of plates. Whenever someone new arrives, they answer the question for every waiting person who is taller than them. The waiting people are always in order: the pile never goes down in height from bottom to top. That is why it is called monotonic : it only moves one way. The order is what makes it cheap. A new person is shorter than some of the pile and not shorter than the rest, and the pile is sorted, so the people they answer are exactly the ones on top. You take them off one by one until the top is not taller, then you put the new person on. ## A worked example Take nums = [4, 2, 6, 5, 1, 7] . We want, for each position, the position of the next smaller number, or -1 if there is none. The pile holds positions. The result is [1, 4, 3, 4, -1, -1] . Positions 4 and 5 are still on the pile at the end: nobody to their right was smaller, so they keep -1 . The last moment in the figure is the one to remember: a single new value answered two waiting values at once. ## How it works For each value, take off every waiting value on top of the pile that is taller than it and record this position as its answer. Then put the new value on the pile. ### Why it is correct Two facts hold at all times. First, everything on the stack is still waiting : nobody to their right so far has been shorter, or they would have been taken off. Second, the stack is sorted , because a new value only goes on once everything taller has left. Now a new value x arrives. Any waiting person taller than x finds their answer here, and it is the first such answer, because they were not taken off earlier. The waiting people that are not taller stay, and since the stack is sorted, they are all below the ones just taken off, so nothing is missed. Without the order we would have to look through the whole stack for every new value. ## Watch it run Press Play or use the arrow keys. The pile is shown as index:value , and result fills in as values are taken off. ## Complexity O(n) Time. Here's why: the for loop runs n times, and the while loop looks like it adds more. But every position goes on the stack once and comes off at most once, so across the whole run there are at most n takings-off. That is at most 2n stack operations in total, which is called amortised O(1) per element: some elements cost a lot, most cost nothing, and the average is a constant. O(n) Space. The stack can hold every position at once, as in [1, 2, 3, 4, 5] . The result array is the output. ## Mistakes and variants - Strict or not. > keeps equal values on the stack and >= takes them off. Decide whether "next smaller" means strictly smaller, and use the one that matches. - Next larger. Flip the comparison to - Every element needs the nearest smaller or larger element on one side. - A brute force where each element walks until it meets something, and the walks overlap. - Answers that are areas, spans or "days until" over a one-dimensional array. Lessons that use it: - Largest Rectangle in Histogram - Maximal Rectangle - Sliding Window Maximum uses the same idea with a queue that can be taken off at both ends. ## Interviewer follow-ups These are the questions that usually come next. Open one to see an answer you could say out loud. "There is a while loop inside a for loop. Why is this not O(n²)?" What they are checking Whether you count the total work instead of multiplying the loop depths. A strong answer Count the stack operations, not the loops. Each position is put on once, and it can be taken off only once after that. So the inner loop runs at most n times over the whole run, even if one single position takes off many. The total is at most 2n operations, so O(n). "The array is circular: after the last element comes the first. What changes?" What they are checking Whether you can keep the idea and change only the walk. A strong answer Go around the array twice, using i % n to read the value, and only put positions on the stack in the first lap. In the second lap the stack still holds the people who found nobody to their right, and they can now find someone on the left side of the array. Time stays O(n), at most 2n steps. "Why does the stack stay sorted? What if two values are equal?" What they are checking Whether you know the one invariant that the whole algorithm stands on. A strong answer A new value goes on only after everything taller than it has been taken off, so the value under it is never taller. That keeps the stack sorted. For equal values, > leaves the equal one on the stack, so the stack can hold equal values next to each other and "next smaller" means strictly smaller. With >= the equal one is taken off, and the answer becomes "next smaller or equal". Pick the one the problem asks for. ## Solution code ### Python ```python class MonotonicStack: def nextSmaller(self, nums): result = [-1] * len(nums) # -1 = nobody shorter stack = [] # indices, values never fall for i, x in enumerate(nums): while stack and nums[stack[-1]] > x: result[stack.pop()] = i stack.append(i) return result ``` --- From Compound Engineer (https://compoundengineer.com), visual lessons for engineers. The page above is the full interactive version.