Monotonic Stack Explained: The O(n) Next-Greater Trick

The monotonic stack has a reputation for being a trick — something you either remember on the day or do not. It is not a trick. It is one idea about waiting, and once you can say that idea in a sentence, a whole family of questions collapses into the same fifteen lines.

The problem it solves

"For each element, find the first larger element to its right." Next greater element, daily temperatures, stock span, the largest rectangle in a histogram — all of them are that question in a costume.

The brute force is honest and obvious: for every index, walk right until you find something bigger. That is O(n²), and on a descending array it really does do n²/2 comparisons rather than getting lucky.

What is wasteful about it is not the search. It is that the same stretch of array gets re-scanned by every index that starts before it. Index 0 walks past indices 1 through 40; index 1 walks the same 39 again. The information was already there the first time.

The intuition

Turn the question around. Instead of each element going out to look for its answer, let each element wait to be answered.

An element with no answer yet is waiting. A new, larger value answers everyone who has been waiting for something smaller than itself — all at once.

Who can still be waiting? Only elements no one has answered yet, which means every value that arrived after an earlier waiting element must have been smaller than it — otherwise it would have settled the earlier one on the way in. So the group of waiting elements is automatically in decreasing order, bottom to top. That ordering is not something you maintain; it is something the rule produces.

And because the most recent arrival is the first one a newcomer has to check, the right container is a stack.

The practical form of this is one line of discipline: before pushing the current value, pop everything smaller than it, and the current value is the answer for each thing you pop.

Watch it run

Watch the stack while the scan moves right. The column only ever holds values that are still unanswered, and it always slopes downward toward the top. When a tall value arrives, watch how many pops it triggers in one step.

That burst of pops is the whole efficiency argument made visible: a single element settling six older ones is six answers produced in six operations, not six separate searches.

The code

def next_greater(nums):
    """For each index, the value of the first larger element to its right."""
    answer = [-1] * len(nums)
    stack = []                                  # indexes; their values decrease
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:    # x settles everyone smaller
            answer[stack.pop()] = x
        stack.append(i)                         # still waiting for its answer
    return answer                               # leftovers keep their -1


def days_until_warmer(temps):
    answer = [0] * len(temps)
    stack = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j                   # the index gap IS the wait
        stack.append(i)
    return answer


print(next_greater([2, 1, 2, 4, 3]))        # [4, 2, 4, -1, -1]
print(next_greater([5, 4, 3]))              # [-1, -1, -1]
print(days_until_warmer([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

The two functions differ by one line. That is the point: the stack does not care what you want out of the pop. Store indexes and you can compute anything at pop time — the value, the distance, the width of a rectangle between two boundaries. Store values instead and the distance questions become impossible, which is why indexes are the default even when you only need the value.

The complexity

Time: O(n). The inner while loop looks like it should make this quadratic, and it does not, for an accounting reason worth saying out loud: each index is pushed exactly once and popped at most once. The total number of stack operations across the entire run is therefore at most 2n, no matter how the while loop is distributed across iterations. One iteration may pop forty things; then forty later iterations pop nothing.

Running the counters on a 100,000-element descending array followed by one large value — the input that maximises the burst — gives 100,001 pushes and 100,000 pops. Linear, on the worst case for the inner loop.

Space: O(n). On a strictly decreasing array nothing is ever popped, so every index is still on the stack when the loop ends. That is the peak, and it is the same input that makes the brute force worst.

Where it goes wrong

• Pushing before popping. Push the current index first and the while loop compares the value against itself. Pop first, push second — the order is the algorithm.
• Getting < and <= backwards with duplicates. < leaves equal values on the stack, so "next strictly greater" is what you get. <= pops them, which answers "next greater or equal". Both are correct implementations of different questions, and the interviewer will have one in mind. Ask.
• Storing values when the question is about distance. answer[j] = i - j cannot be written if j was never kept.
• Forgetting the unanswered tail. A solution that only writes answers inside the pop and never initialises the array leaves those positions undefined.
• Assuming it only works rightward. For "previous greater element", run the same loop over reversed(nums), or scan left to right and read the value underneath the current one at push time. Same stack, different moment of reading it.

How to say it in an interview

Name the pattern, then justify the linearity before you are asked:

"Each element is looking for the first larger value to its right, so instead of searching forward from every index I will keep a stack of indexes whose answers are still pending. That stack stays in decreasing order by construction, because anything larger than a pending element would already have resolved it. When a new value arrives, it pops every smaller pending index and is their answer. Each index is pushed once and popped once, so that is O(n) time and O(n) space despite the nested loop."

Then, when you write it, say "pop, then push" as you type the two lines. Getting that order right under pressure is most of what separates a working monotonic stack from a broken one.