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) |
Put a group of people in a line by height, from left to right. Imagine that you must track, for each person, who the next taller person is. A brute-force method is this: for every person, scan forward through all the people after them until a taller person appears. This is a scan inside a scan, which is O(n) work, up to n times, so O(n²) in total.
A monotonic stack does this in one pass, because it keeps a strict discipline about who it holds. Walk the line from left to right and hold a stack of people. Keep the stack so that the heights only increase from bottom to top, or only decrease from bottom to top, based on the question. When the next person arrives, remove from the stack anyone who is now shorter than this new person. Those people have just found their next taller person: the new arrival. When no one left in the stack is shorter, push the new person on top and continue. At any moment, everyone still in the stack is in a line sorted by height. Only the people who are still relevant to a future comparison stay in the stack. Anyone whose question is answered is removed immediately.
The stack (or, for a sliding window instead of the whole array, a monotonic queue built on a deque, which is a Doubly Linked List usable from both ends) always stays sorted by its construction. It is never sorted at the start and never sorted again. You keep it in order: you remove anything that would break the order before you admit anything new.
Next Greater Element and Sliding Window Maximum
structure MonotonicStack:
// built on a plain Stack from Stack & Queue. push/pop/peek, O(1) each.
items // the heights only increase or only decrease, from bottom to top
structure MonotonicDeque:
// built on a Doubly Linked List, used from both ends at the same time
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 the next greater element of j
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 is now outside the current window
if i >= k - 1:
result.append(arr[front of deque]) // the front always holds the max of the current window
return resultThe while loop inside the for loop looks like it could be O(n²). This is the same shape as the shrink loop in Sliding Window, and the same trap that Big-O Notation warns about: a nested loop that is not actually O(n²) once you count the total work instead of the worst case per iteration. Look at the total pushes and pops instead of the loop shape. Each index is pushed onto the stack or deque exactly one time (when the outer loop reaches it). Each index is popped a maximum of one time (whichever branch pops it, it is gone for good; it is never pushed again). The total pushes plus pops across the full run is a maximum of 2n, not n².
| Operation | Time | Space | Why |
|---|---|---|---|
| Next Greater Element (monotonic stack) | O(n) total | O(n) | There are n pushes and a maximum of n pops across the full run. The total iterations of the inner while loop, summed over every outer step, are limited by n, not n per step. |
| Sliding Window Maximum (monotonic deque) | O(n) total | O(k) — the deque never holds more indices than the current window | This is the same amortized argument, doubled. Each index is pushed to the back one time, and popped from either the back (value evicted) or the front (aged out) a maximum of one time. |
| 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 walks forward again (or scans the window again) from the start. This is exactly the repeated work that a monotonic stack or queue exists to skip, the same story as Sliding Window versus a new sum of every subarray. |
Miscounting the cost as O(n²) from the loop shape alone
The nested-loop shape is misleading on its own. The shrink loop in Sliding Window taught the same lesson. What actually limits the cost is that every element is pushed exactly one time and popped a maximum of one time across the full run. So the total inner-loop work over the whole algorithm is O(n), not O(n) per outer step. Judge by the total push and pop budget, not by whether a while loop is inside a for loop.
Forgetting to evict expired indices from the front of a monotonic deque
A monotonic deque for a sliding window needs two separate evictions: a back-eviction for value order, and a front-eviction to stay inside the window. If you skip the front check, a stale index that left the window long ago, but was never beaten in value, stays at the front forever. It is reported as the current window maximum with no error, even though it is no longer in the window. This is a Sliding-Window-style boundary bug. The left edge of the window must actively expire old entries, the same discipline as a shrink of 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 the "next greater" question of the smaller value is now answered. Next Smaller Element needs the opposite: an increasing stack, pop while the top is bigger than the incoming value. If you flip the comparison by mistake, you get a stack that is monotonic in the wrong direction. It answers a completely different question than the one asked, usually with no crash.
Missing an empty-stack/deque check before peeking or popping
The while condition itself (stack is not empty and ...) must check for empty first. Short-circuit evaluation works only if the empty check comes before the value check, not after. This check is easy to drop when the loop also has an eviction condition to manage. If you drop it, a normal "nothing left to evict" case becomes a peek on an empty structure. This is the same underflow bug that Stack & Queue describes, but easier to miss inside a harder loop.
Sign in to mark problems done — progress syncs across devices.