The Monotonic Stack: Next Greater Element in O(n)
AlgorithmsKeep a stack whose values are always sorted. When a new value breaks the order, pop until it fits - each pop answers a question about the popped item. Every element is pushed and popped once, so it is O(n).
A queue of people ordered by height at a concert. When a taller person arrives, everyone shorter in front of them can never see the stage past this newcomer - so they are done being relevant and leave the line.
The question it answers. 'For each element, where is the next greater (or smaller) element?' The obvious solution compares every pair, O(n^2). The monotonic stack does it in one pass.
The trick. Walk left to right keeping a stack of indices whose values are in decreasing order (for next-greater). For each new value, while the stack's top is smaller than it, that top has just found its answer: the current element. Pop it and record the result. Then push the current index.
def next_greater(nums):
ans = [-1] * len(nums)
stack = [] # indices, values decreasing
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
ans[stack.pop()] = x # x is the next greater for that index
stack.append(i)
return ans
# next_greater([2, 1, 5, 3, 4]) -> [5, 5, -1, 4, -1]Why it is O(n). Each index is pushed once and popped at most once, so the inner while does O(n) work in total across the whole loop, even though it looks nested.
Flip the direction. Next *smaller*: keep the stack increasing. Previous greater/smaller: read the stack top *before* pushing. Circular arrays: loop 2n times with i % n. Always store indices, not values, so you can compute distances.
Classic uses. Daily temperatures (days until a warmer day, answer is i - popped_index), stock span, valid parenthesis matching, and the largest rectangle in a histogram: when a bar is popped, its width extends from the new stack top to the current index, so its area is height * (i - stack[-1] - 1).
Recognising it. Phrases like 'next greater', 'previous smaller', 'span', 'how many days until' and 'nearest to the left that is bigger' signal a monotonic stack. If you catch yourself writing a nested loop that scans outward from each element until a condition, ask whether a stack can remember the unresolved ones.
Edge cases. Equal values (decide whether < or <= pops), an empty stack (use -1 or a sentinel), and a final flush: elements left on the stack have no answer (or extend to the end, in the histogram problem).
- Stack of indices kept in sorted (monotonic) order.
- A new element pops everything it beats; each pop resolves the popped item.
- Each element is pushed and popped once, so the total is O(n).
- Decreasing stack = next greater; increasing stack = next smaller.
- Store indices so you can compute distances and widths.
Curated Curation & Deep Insights
ScaleDojo CertifiedOur system architects are vetting high-quality, authorized video guides for The Monotonic Stack: Next Greater Element in O(n) with zero third-party platform links.
We are preparing premium, zero-competitor deep-dives for The Monotonic Stack: Next Greater Element in O(n). Authorized reading references will appear automatically.