Monotonic Stack & Queue

Intermediate · 22 min read · Problem-Solving Patterns, Stacks & Queues

Next greater element, histograms and sliding-window maximum in O(n).

"For each day, how many days until a warmer temperature?" The brute force looks right from each day until it finds a warmer one — O(n²) on a long cold spell. A monotonic stack answers it in one pass.

The idea: a stack of things still waiting for an answer

Walk left to right. The stack holds indexes that haven't found their next greater element yet. When a new element arrives, it is the answer for every waiting element smaller than it — pop them all and record it. Then the new element joins the waiting list.

Worked problems

Walk the array twice (indexes 0 … 2n − 1, using i % n), but only push during the first lap — the second lap just resolves the elements still waiting.

The monotonic deque: sliding-window maximum

A heap would give O(n log k). A deque of indexes with decreasing values gives O(n): the front is always the window's maximum. When a new element arrives, smaller elements at the back can never be a maximum again (the new one is bigger and stays longer), so drop them.

Practice ladder

Interview questions

Why is the monotonic stack solution O(n) even though there's a while loop inside the for loop?
How does the largest-rectangle-in-histogram algorithm know each bar's width?

Key takeaways

A monotonic stack holds indexes still waiting for their next greater/smaller element; a new element resolves the ones it beats.
Pop condition and strictness decide the variant; storing indexes gives distances and widths.
Each element is pushed and popped once → O(n).
Contribution counting: element × (left choices) × (right choices), strict on one side only.
Monotonic deque: window maximum in O(n) — drop dominated elements from the back, expired ones from the front.

Previous: Stack Patterns · Next: Heaps: Top-K, K-Way Merge, Two Heaps