Monotonic stack in Python: next greater element in O(n) and the loop to memorise

Short answer. A monotonic stack is a stack that stays sorted from bottom to top. It finds the next greater or next smaller element for every index. One pass, O(n). The trigger words are "next greater", "previous smaller", "how many days until" and "largest rectangle". Below: the loop, Python code, and its two most common problems.

What is a monotonic stack?

A normal stack lets you push anything. A monotonic stack pops first. Before pushing a value, you pop everything that would break the order.

Keep it decreasing. The top is then the closest larger value. Keep it increasing, and the top is the closest smaller value.

Each element is pushed once and popped at most once. So the whole pass is O(n), nested while loop included.

When does a problem need a monotonic stack?

• "Next greater element" or "next smaller element" for each index.
• "How many days until a warmer temperature."
• "Largest rectangle in a histogram" and "trapping rain water".
• "Remove k digits to make the smallest number."

The shared shape: find the nearest neighbour that beats the current value. Nested loops give O(n²). The stack gives O(n).

How does the monotonic stack loop work?

• Walk the array left to right. The stack holds indexes, not values.
• While the current value beats the value at the top, pop. The popped index has just found its answer: the current index.
• Push the current index.
• Indexes left on the stack at the end have no answer. Use -1.

Storing indexes lets you compute distances and read values. Storing values loses the position.

What does the monotonic stack look like on an example?

Take [2, 1, 4, 3]. Push index 0 (value 2). Value 1 does not beat 2, push index 1. Stack holds 2, 1 from bottom to top.

Value 4 arrives. It beats 1: pop index 1, its answer is 4. It beats 2: pop index 0, its answer is 4. Push index 2.

Value 3 does not beat 4, push index 3. End of input. Indexes 2 and 3 stay on the stack and get -1. Result: [4, 4, -1, -1]. Four pushes, two pops, no wasted work.

How do you write a monotonic stack in Python?

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                       # indexes, values decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

def daily_temperatures(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
        stack.append(i)
    return answer

Change the comparison to > and you get next smaller. Walk right to left and you get previous greater or smaller.

Which direction and which comparison does a monotonic stack need?

Question	Walk	Pop while top is	Stack order
Next greater	Left to right	smaller than current	Decreasing
Next smaller	Left to right	larger than current	Increasing
Previous greater	Left to right, read top before push	smaller than current	Decreasing
Previous smaller	Left to right, read top before push	larger than current	Increasing

For "previous" questions, read the top after popping and before pushing. For "next" questions the answer is assigned to the popped index.

How does the stack solve Largest Rectangle in Histogram?

Each bar extends left and right until a shorter bar. The rectangle width is the gap between those two bars.

Keep an increasing stack of indexes. When a shorter bar arrives, pop the taller one. Its right boundary is the current index. Its left boundary is the new stack top. Area is height times the width between them. Append a bar of height 0 to flush the stack.

One pass, O(n). The brute force is O(n²).

What mistakes break a monotonic stack?

• Storing values instead of indexes, then needing a distance.
• Using <= where < was needed. Equal values change which neighbour counts.
• Forgetting to flush the stack at the end of a histogram problem.
• Reading the answer at the wrong moment for "previous" questions.

How do you explain a monotonic stack in an interview?

Say the question is about the nearest bigger neighbour. Say a brute force costs O(n²). Then say: keep unanswered indexes on a decreasing stack. Each new value answers the ones it beats.

Finish with the amortised argument. Every index enters once and leaves once, so the loop is linear. Interviewers wait for that sentence.

Drill this pattern against its neighbours on the monotonic stack page. The sliding window version is on the monotonic deque page.

FAQ

What is the difference between a monotonic stack and a monotonic deque?

A deque also removes from the front. So it can drop elements that left a window. A stack only handles the "nearest neighbour" family.

Can a monotonic stack handle a circular array?

Yes. Walk the indexes twice, from 0 to 2n - 1. Use i mod n. Only push during the first pass or push both, both work.

Why is it O(n) with a while loop inside a for loop?

The while loop pops. You cannot pop more times than you pushed. Total pushes are n, so total pops are at most n.