Monotonic Stack and Deque

What “monotonic” means here

You already know a stack from the stacks-and-queues lesson: a collection with one rule, last in, first out, where you push onto the top and pop from the top, both in O(1) time. A monotonic stack adds a discipline to what the stack is allowed to hold. “Monotonic” means “always moving in one direction,” and here it describes the values sitting in the stack: they are kept in sorted order, either always increasing or always decreasing from bottom to top.

The stack does not sort itself by magic. We keep it ordered by hand: every time we are about to push a new value, we first pop off any values that would break the order, and only then push. That single act of popping is not wasted work. Each value we pop is one whose question just got answered by the newcomer that displaced it. That is the whole idea, and it turns a family of problems that look quadratic into linear scans.

The canonical use: next greater element

The classic problem is next greater element: for each item in a list, find the first item to its right that is strictly larger. If nothing to the right is larger, the answer is -1. For [2, 1, 2, 4, 3] the answers are [4, 2, 4, -1, -1]: the 2 at index 0 is first beaten by the 4, the 1 is beaten by the very next 2, and the 4 and the final 3 have nothing larger ahead of them.

The obvious method compares every item against everything to its right, which is O(n^2). The monotonic stack does it in one pass. Walk the list left to right and keep a stack of items that are still waiting for their answer. Crucially we store indices, not values, so we can write the answer into the right slot (and later measure distances). We keep the stack’s values in decreasing order from bottom to top. When the current value is larger than the value at the top index, that top item has found its next greater element: pop it and record the current value as its answer. Repeat until the top is no longer smaller, then push the current index.

def next_greater(nums: list[int]) -> list[int]:
    n = len(nums)
    answer = [-1] * n          # default: nothing bigger to the right
    stack: list[int] = []      # indices whose answer is still pending
    for i in range(n):
        # current value resolves every smaller pending value on top
        while stack and nums[stack[-1]] < nums[i]:
            j = stack.pop()    # index whose answer is nums[i]
            answer[j] = nums[i]
        stack.append(i)        # i now waits for its own next greater
    return answer

print(next_greater([2, 1, 2, 4, 3]))   # -> [4, 2, 4, -1, -1]
print(next_greater([5, 4, 3, 2, 1]))   # -> [-1, -1, -1, -1, -1]

Whatever is left on the stack at the end never found a larger value to its right, so those slots keep their -1. That is why we seed answer with -1 up front.

A step-by-step trace

Walk the code on [2, 1, 2, 4, 3]. The stack holds indices, and each row shows the state as we arrive at index i: what we pop and resolve, and the stack of pending indices afterward. Reading the values under those indices from bottom to top always stays non-increasing, which is the invariant that makes the pops valid.

At i = 2 the incoming 2 is larger than the pending 1, so index 1 is resolved with 2; the 2 at index 0 is not smaller than the incoming 2 (we compare with strict <), so it stays. At i = 3 the 4 sweeps off both pending 2s at once. When the walk ends, indices 3 and 4 remain unresolved and keep -1.

Why this is O(n): the amortized argument

There is an inner while loop, so it is fair to worry that this is secretly quadratic. It is not, and the reason recurs across many problems.

Look at the lifetime of a single index. It is pushed onto the stack exactly once, when the outer loop reaches it, and popped at most once, when some later value resolves it, after which it is gone for good. So across the entire run the total number of pushes is n and the total number of pops is at most n. One step of the outer loop might pop many items while another pops none, but the popping is “charged” against pushes that already happened, so the sum of all inner-loop iterations is at most n. Total work is O(n) time, plus O(n) space for the stack and the answer list. This accounting, where a costly step is paid for by cheap steps elsewhere, is called amortized analysis, and “each element is pushed once and popped once” is its signature.

Storing indices unlocks distances

Because we stored indices rather than values, the same skeleton answers “how far away is the next greater value?” with a one-character change: instead of writing nums[i] as the answer, write the gap i - j. A common phrasing asks, given daily temperatures, how many days until a warmer one.

def days_until_warmer(temps: list[int]) -> list[int]:
    n = len(temps)
    answer = [0] * n           # 0 means no warmer day ahead
    stack: list[int] = []      # indices of days awaiting a warmer day
    for i in range(n):
        while stack and temps[stack[-1]] < temps[i]:
            j = stack.pop()
            answer[j] = i - j  # distance in days, not the temperature itself
        stack.append(i)
    return answer

print(days_until_warmer([73, 74, 75, 71, 69, 72, 76, 73]))
# -> [1, 1, 4, 2, 1, 1, 0, 0]

The structure is identical to next_greater; only the value written into answer changed. That is exactly why storing indices is the more flexible default: an index recovers its value with temps[j], but a stored value cannot recover its position.

The mirror image, previous smaller element, flips the comparison. To find the nearest smaller value to each item’s left, keep an increasing stack and, before pushing i, pop everything on top that is greater than or equal to nums[i]; whatever remains on top is the previous smaller element.

def previous_smaller(nums: list[int]) -> list[int]:
    answer: list[int] = []
    stack: list[int] = []      # indices, values increasing bottom to top
    for i in range(len(nums)):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()        # too big to be "smaller"; discard
        answer.append(nums[stack[-1]] if stack else -1)
        stack.append(i)
    return answer

print(previous_smaller([2, 1, 2, 4, 3]))   # -> [-1, -1, 1, 2, 2]

The dividing line is direction and comparison. Next-greater scans and resolves items as a larger value arrives; previous-smaller reads the surviving top as the answer before pushing. Both are one pass, both are O(n).

A second application: largest rectangle in a histogram

A histogram is a row of bars of given heights, each one unit wide. The largest rectangle that fits inside is bounded on each side by the first bar shorter than it, and a monotonic increasing stack of indices finds those two boundaries for every bar in a single pass.

Keep the stack’s heights increasing. When a bar shorter than the top arrives, the popped bar can extend no further right, so we settle its rectangle now: its height is the popped bar, and its width runs from just after the new top of the stack up to the current index. A sentinel 0 appended at the end forces every remaining bar to be settled.

def largest_rectangle(heights: list[int]) -> int:
    stack: list[int] = []      # indices with increasing heights
    best = 0
    for i, h in enumerate(heights + [0]):   # trailing 0 flushes the stack
        while stack and heights[stack[-1]] > h:
            top = stack.pop()               # this bar can grow no wider
            height = heights[top]
            # left edge is the bar now on top; if empty, the rectangle
            # reaches the very start, so width is the full span up to i
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, height * width)
        stack.append(i)
    return best

print(largest_rectangle([2, 1, 5, 6, 2, 3]))   # -> 10
print(largest_rectangle([2, 4]))                # -> 4

For [2, 1, 5, 6, 2, 3] the winner is height 5 and 6 spanning two columns for area 10. Each index is pushed once and popped once, so despite the nested loop this is O(n) time and O(n) space, the same amortized argument as before.

Monotonic deque: the sliding-window maximum

Some problems need the maximum of a moving window of fixed size k: as the window slides one step right, one value enters at the back and one leaves at the front. A plain rescan of each window is O(n·k). The fix is a monotonic deque, using collections.deque (the double-ended queue from the earlier lesson, O(1) on both ends).

We hold indices in the deque, kept so their values are in decreasing order from front to back. Two rules maintain that and the window:

• Back: before adding the new index, pop from the back every index whose value is less than or equal to the incoming value. Those can never be the maximum again, because the newcomer is at least as large and stays in the window longer.
• Front: if the index at the front has slid out of the window (it is more than k - 1 behind the current index), pop it from the front.

After both rules, the front of the deque always holds the index of the current window’s maximum.

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()   # indices, values decreasing front -> back
    result: list[int] = []
    for i in range(len(nums)):
        # drop smaller values at the back; they cannot win while nums[i] stands
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
        dq.append(i)
        # drop the front if it has left the window
        if dq[0] <= i - k:
            dq.popleft()
        # once the first full window is formed, record its max
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# -> [3, 3, 5, 5, 6, 7]

Every index enters the deque once and leaves once, from either end, so the whole scan is O(n) time. The deque never holds more than k indices, giving O(k) extra space. The through-line with the monotonic stack is exact: we discard candidates the moment a better one makes them irrelevant, and we never look back.

Common pitfalls

• Storing values when you need indices. A value on the stack cannot tell you where it came from, so distance questions (“how many days,” widths in the histogram) and window-expiry checks become impossible. Store indices and read nums[j] when you want the value. It is the safe default.
• Strict versus non-strict comparison for duplicates. Whether you pop on < or <= decides how equal values are treated, and the right choice depends on the question. In next_greater we want strictly greater, so we pop on < and let an equal value stay pending. In the sliding-window deque we pop the back on <= so a later equal value replaces an older one, which keeps the deque short and is still correct because either copy is a valid maximum. Getting this backward produces answers that are off only on inputs with repeats, which is easy to miss.
• Reading the answer at the wrong moment. Next-greater writes an answer as it pops; previous-smaller reads the surviving top before it pushes. Mixing the two timings gives a stack that is correct but consulted on the wrong step.
• Forgetting to flush the stack. Items still pending at the end have no answer from the right. Either seed the answer array with the sentinel (as next_greater does) or append a sentinel value that forces every remaining item to resolve (as the histogram does). Skip both and the last few answers are simply wrong.
• Checking the deque window against the wrong bound. The front index is expired when dq[0] <= i - k. An off-by-one here (< i - k, or comparing to i - k + 1) keeps a stale index one step too long and corrupts the reported maximum.

Big-O summary

n is the number of items and k the window size. Every routine here is a single left-to-right pass in which each index is pushed once and popped at most once.

Practice

1. Write next_smaller(nums) that returns, for each item, the first strictly smaller value to its right, or -1 if there is none. Start from next_greater and change only the comparison. Test it on [4, 2, 3, 1] and confirm you get [2, 1, 1, -1].

2. Adapt the sliding-window routine into min_sliding_window(nums, k) that reports the minimum of each window. Decide whether the back-popping comparison should flip to >=, and explain in a comment why the deque must now stay increasing. Check it on [1, 3, -1, -3, 5, 3, 6, 7] with k = 3, expecting [-1, -3, -3, -3, 3, 3].

3. Using the amortized argument, explain in two or three sentences why largest_rectangle is O(n) even though it has a while loop nested inside a for loop. Point to the exact lines where each index is pushed and where it is popped.