Monotonic Stack & Queue
Quick reference
| Next Greater Element (monotonic stack) | O(n) total |
| Sliding Window Maximum (monotonic deque) | O(n) total |
| Brute force (for comparison): rescan for the next greater/max on every step | O(n²) or O(n·k) |
Line up a group of people by height, left to right, and imagine you're trying to track, for each person, who the next taller person is. A brute-force way is: for every person, scan forward through everyone after them until a taller one shows up. That's a scan inside a scan — O(n) work, up to n times, O(n²) overall.
A monotonic stack does it in one pass by staying disciplined about who it keeps around. Walk the line left to right holding a stack of people, always kept shortest-at-bottom... no — kept so heights only ever increase as you go from bottom to top, or only ever decrease, depending on the question. When the next person arrives, kick out of the stack anyone who is now shorter than this new person — they've just found their "next taller person": the new arrival. Once nobody left in the stack is shorter, push the new person on top and move on. Everyone still in the stack at any moment is standing in a lineup sorted by height, and only the people still relevant to some future comparison stay in it — anyone whose question just got answered is evicted immediately.
The stack (or, for a sliding window instead of the whole array, a monotonic queue built on a deque — a Doubly Linked List usable from both ends) always stays sorted by construction: never sorted upfront, never re-sorted, just kept in order by evicting anything that would break it before anything new is admitted.
Next Greater Element and Sliding Window Maximum
structure MonotonicStack:
// built on a plain Stack from Stack & Queue — push/pop/peek, O(1) each
items // heights only ever increase or only ever decrease, bottom to top
structure MonotonicDeque:
// built on a Doubly Linked List, used from both ends at once
list // push/pop at the head AND the tail, both O(1)Next Greater Element — decreasing stack of indices, O(n)
function nextGreaterElements(arr):
answer = array of -1, same length as arr // default: no greater element found
stack = empty Stack // holds indices, values stay decreasing bottom to top
for i from 0 to length(arr) - 1:
while stack is not empty and arr[top of stack] < arr[i]:
j = pop(stack) // arr[i] is j's next greater element
answer[j] = arr[i]
push(stack, i)
return answerSliding Window Maximum — decreasing deque of indices, O(n)
function slidingWindowMax(arr, k):
result = []
deque = empty MonotonicDeque // holds indices, values decreasing front to back
for i from 0 to length(arr) - 1:
while deque is not empty and arr[back of deque] < arr[i]:
popBack(deque) // a smaller value can never win once arr[i] is in the window
pushBack(deque, i)
if front of deque <= i - k:
popFront(deque) // that index has fallen outside the current window
if i >= k - 1:
result.append(arr[front of deque]) // front always holds the current window's max
return resultThe while loop nested inside the for loop looks like it could be O(n²) — same shape as Sliding Window's shrink loop, and the same trap Big-O Notation warns about: a nested loop that isn't actually O(n²) once you count total work instead of worst-case-per-iteration. Look at total pushes and pops instead of the loop shape: each index is pushed onto the stack or deque exactly once (when the outer loop reaches it) and popped at most once (whichever branch pops it, it's gone for good — it never gets pushed again). Total pushes plus pops across the entire run is at most 2n, not n².
| Operation | Time | Space | Why |
|---|---|---|---|
| Next Greater Element (monotonic stack) | O(n) total | O(n) | n pushes, at most n pops across the whole run — the inner while loop's total iterations, summed over every outer step, is bounded by n, not n per step. |
| Sliding Window Maximum (monotonic deque) | O(n) total | O(k) — the deque never holds more than the current window's worth of indices | Same amortized argument, doubled: each index is pushed to the back once, and popped from either the back (value evicted) or the front (aged out) at most once. |
| Brute force (for comparison): rescan for the next greater/max on every step | O(n²) or O(n·k) | O(1) extra | Without eviction, every position re-walks forward (or re-scans the window) from scratch — exactly the repeated work a monotonic stack/queue exists to skip, the same story as Sliding Window versus resumming every subarray. |
Miscounting the cost as O(n²) from the loop shape alone
The nested-loop shape is misleading on its own — Sliding Window's shrink loop taught the same lesson. What actually bounds the cost is that every element is pushed exactly once and popped at most once across the entire run: total inner-loop work over the whole algorithm is O(n), not O(n) per outer step. Judge by the total push/pop budget, not by whether a while loop sits inside a for loop.
Forgetting to evict expired indices from the front of a monotonic deque
A monotonic deque used for a sliding window needs two separate evictions: back-eviction for value order, front-eviction for staying inside the window. Skip the front check and a stale index that fell out of the window weeks ago — but never got beaten in value — sits at the front forever, silently reported as the current window's max even though it isn't in the window anymore. This is a Sliding-Window-flavored boundary bug: the window's left edge has to actively expire old entries, the same discipline as shrinking a variable-size window from the left.
Direction backward — decreasing stack for next-greater, increasing for next-smaller
Next Greater Element needs a decreasing stack: pop while the top is smaller than the incoming value, because a smaller value's "next greater" question just got answered. Next Smaller Element needs the opposite — an increasing stack, popping while the top is bigger than the incoming value. Flipping the comparison by mistake produces a stack that's monotonic in the wrong direction and answers a completely different question than the one asked, usually without crashing.
Missing an empty-stack/deque check before peeking or popping
The while condition itself (stack is not empty and ...) has to check emptiness first — short-circuit evaluation only works if the emptiness check comes before the value check, not after. It's an easy check to drop once the loop also has an eviction condition to worry about, and dropping it turns a normal 'nothing left to evict' case into a peek on an empty structure — the same underflow bug Stack & Queue calls out, just easier to miss inside a trickier loop.
Sign in to mark problems done — progress syncs across devices.