Monotonic stack
In one line
Keep a stack whose values are always increasing or decreasing; when a new element breaks the order, everything it pops has just found its next greater (or smaller) element, giving O(n) for problems that look O(n^2).
What it is
A monotonic stack is an ordinary stack with one rule: the values (or the values at the stored indices) stay in sorted order from bottom to top. Before pushing a new element, you pop every element that would break that order.
The popping is where the answers come from. In a decreasing stack, when a new value is larger than the top, the new value is the first larger element to the right of the top, its 'next greater element'. This answers a whole family of questions: next greater element, days until a warmer temperature, stock span, and the largest rectangle in a histogram.
Why interviewers ask
Interviewers love this pattern because the brute force (for each element, scan to the right) is obvious and O(n^2), and the O(n) solution requires a real insight. Daily Temperatures, Next Greater Element and Largest Rectangle in Histogram are frequent questions. You are tested on choosing increasing vs decreasing, storing indices, and explaining why each element is pushed and popped once.
How it works
- 1Decide what you are looking for. Next greater to the right: keep a decreasing stack (pop smaller values). Next smaller to the right: keep an increasing stack (pop larger values).
- 2Store indices, so you can compute distances and write answers into the right positions.
- 3For each index i: while the stack is not empty and the new value beats the value at the top, pop the top j. Element i is the answer for j (for example, answer[j] = i - j days).
- 4Push i. Everything still in the stack is waiting for its answer.
- 5After the scan, indices left in the stack have no next greater (or smaller) element; give them the default (0 or -1).
- 6Each index is pushed once and popped at most once, so the total work is O(n).
Worked example · Daily temperatures [73, 74, 75, 71, 69, 72, 76, 73]
- i = 0 (73): push. Stack [0]. i = 1 (74): 74 > 73, pop 0, answer[0] = 1. Push 1.
- i = 2 (75): pop 1, answer[1] = 1. Push 2. i = 3 (71): smaller, push. i = 4 (69): push. Stack [2, 3, 4] (75, 71, 69).
- i = 5 (72): pop 4 (69), answer[4] = 1; pop 3 (71), answer[3] = 2; 75 is not less than 72, stop. Push 5. Stack [2, 5].
- i = 6 (76): pop 5 (72), answer[5] = 1; pop 2 (75), answer[2] = 4. Push 6. i = 7 (73): push. Stack [6, 7].
- Indices 6 and 7 never find a warmer day: answer 0. Result [1, 1, 4, 2, 1, 1, 0, 0].
Picture it
Imagine people standing in a line looking right, each waiting to see someone taller. When a tall person arrives, every shorter person at the back of the waiting group has found their answer and leaves. The waiting group is always ordered from tallest to shortest.
Reference code
def daily_temperatures(temps):
answer = [0] * len(temps)
stack = [] # indices still waiting for a warmer day
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
answer[j] = i - j # day i is j's next warmer day
stack.append(i)
return answer
def largest_rectangle(heights):
stack = [] # indices with increasing heights
best = 0
for i, h in enumerate(heights + [0]): # 0 at the end flushes the stack
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
Both functions are O(n) time and O(n) space. In largest_rectangle, the appended 0 forces every remaining bar to be popped at the end; for [2, 1, 5, 6, 2, 3] it returns 10 (bars 5 and 6, width 2).
Key patterns
Next greater element
When: First larger value to the right (or distance to it)
How: Decreasing stack of indices; on pop, the current index is the answer for the popped one.
Previous smaller / greater
When: Stock span, nearest smaller to the left
How: Scan left to right; after popping, the new top (if any) is the previous greater or smaller for the current index.
Largest rectangle in histogram
When: Max area of bars, maximal rectangle in a 0/1 matrix
How: Increasing stack; when a bar is popped, its rectangle spans from just after the new top to just before i. Add a 0 sentinel to flush the stack.
Circular arrays
When: Next greater element in a circular list
How: Loop i from 0 to 2n - 1 using i % n; only push during the first pass.
Remove digits greedily
When: Remove k digits to make the smallest number
How: Increasing stack of digits; pop while the top is larger than the new digit and removals remain.
Real-world use
Stock span in trading tools
The stock span problem comes from finance: the span of a day is how many consecutive days up to and including today had a price at or below today's. A monotonic stack computes it for each new price in amortised O(1) instead of rescanning history.
Image processing and layout
Finding the largest empty rectangle in a binary image or on a page (for placing a label or ad) runs largest-rectangle-in-histogram on each row, a monotonic stack algorithm that is O(rows * columns).
Compilers and parsers
Operator-precedence parsing keeps operators on a stack ordered by precedence; when a lower-precedence operator arrives, higher ones are popped and applied, which is a monotonic stack on precedence.
Line-of-sight and skyline checks
Deciding which buildings along a street are visible from one end, or which apartments have an unobstructed view, can be computed in one pass with a stack of increasingly tall buildings, popping those hidden behind a taller one.
In a project
A weather app wants to show, for each of the next 14 days, how many days until it gets warmer, and the same for 10 years of historical daily data in an analytics view.
- Load temperatures as an array in date order.
- Scan once with a decreasing stack of indices; pop and fill answers whenever a warmer day arrives.
- Leave 0 for days with no warmer day in range and display them as 'no warmer day ahead'.
- Unit-test runs of equal temperatures to confirm an equal day does not count as warmer (strict < when popping).
Impact: Ten years of data (about 3,650 days) is processed in about 7,300 stack operations instead of millions of comparisons in the worst case, so the analytics view loads instantly and the same code serves the mobile forecast.
Trade-offs
Use it when
- For each element you need the nearest greater or smaller element to the left or right
- The brute force scans outward from each element (O(n^2))
- Areas or spans bounded by the nearest smaller bars on each side
Avoid it when
- You need the max or min of a sliding window: that needs removal from the old end too, so use a monotonic deque
- You need the k-th largest, not the nearest greater: use a heap
- Arbitrary range max queries: use a sparse table or segment tree
Cost: Time O(n) amortised: each index is pushed once and popped at most once. Space O(n) in the worst case (for example, strictly decreasing input for a next-greater scan).
Common mistakes
- Choosing the wrong order: next greater needs a decreasing stack, next smaller needs an increasing one.
- Storing values instead of indices, which loses positions needed for distances and widths.
- Getting < vs <= wrong with duplicates; decide whether equal values count as 'greater' and test with repeated numbers.
- In the histogram problem, computing width as i - popped instead of i - new_top - 1, or forgetting the final sentinel.
- Calling it O(n^2) because of the nested while loop instead of explaining the amortised O(n).
Interview questions
Quick revision
- Next greater: decreasing stack; next smaller: increasing stack.
- Store indices; answer assigned when an index is popped.
- Leftovers in the stack have no answer (0 or -1).
- Each index pushed once, popped once: O(n).
- Histogram: width = i - stack[-1] - 1 after popping (or i if empty).
- Sentinel 0 at the end flushes the stack.
- Circular: loop 2n with i % n.
- Sliding window max needs a deque, not a stack.
Check yourself
1. What are the next greater elements of [2, 1, 2, 4, 3] (use -1 if none)?
2. To find the next greater element for each index, the stack should hold values that are...
3. What is the largest rectangle area for heights [2, 4]?
4. What is the worst-case extra space of a monotonic stack scan over n elements?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.