Monotonic stack and deque

Problem

"For each day, how many days until a warmer one?" Checking forward from every day is O(n²) on a steadily falling run. The observation that saves you: a day that is still waiting for something warmer only needs to be compared with new arrivals, and the moment one arrival is warmer than the most recently waiting day, it is warmer than every waiting day colder than that, too. So waiting days can be kept in a stack in decreasing temperature order, and each arrival resolves a run from the top.

Intuition

Imagine people standing in a queue facing a stage, each with a height. A tall person arriving makes every shorter person standing right in front of them irrelevant for the purpose of "who can see the stage", because the newcomer blocks them for anyone further back. The stack is the list of people still relevant. Each person enters once and leaves once, so the work is linear even though one arrival may remove many.

The direction (stack decreasing or increasing) is chosen by the question. "Next greater" keeps items that have not yet found a greater one, so values decrease from bottom to top: any larger arrival pops from the top. "Next smaller" and rectangle problems use the mirror image.

Green bars carry the largest rectangle: height 3 across 3 bars, area 9. The line marks its top; the shorter bars on either side are what stops it growing.

Mechanics

The invariant

The stack holds, bottom to top, the indices that have not yet been answered, and their values are monotone (strictly decreasing for next-greater). Before pushing index i, pop every index whose value is beaten by values[i]; each pop is an answer for that index, with i as its next greater element. Why correct: an index is popped by the first later value that beats it, which is by definition its next greater element, and nothing between could have beaten it, or it would have been popped earlier. Indices left at the end have no greater element. Because every index is pushed once and popped once, total work is O(n).

Largest rectangle

Keep bar indices with increasing heights. When bar i is not taller than the top, the top bar's rectangle cannot extend any further right: i is its first shorter-or-equal neighbour on the right. Its left limit is the new top of the stack after popping (the nearest shorter bar on the left), so its widest rectangle spans (new top, i) exclusive and has area height × (i − new top − 1). A sentinel height of 0 at the end flushes everything. The maximum of these areas is the answer, because the best rectangle has some bar as its minimum, and that bar's widest rectangle is the one computed.

The deque for window maximum

A fixed window's running sum can be undone, but a maximum cannot. Keep a deque of indices whose values decrease from front to back. A new value pops every smaller value from the back: those can never be the maximum while the newcomer is in the window, and it outlives them. The front is the maximum; pop it from the front when its index leaves the window. Each index enters and leaves once.

Each row is the stack after that day, bottom on the left. The amber box is the day just pushed; a shorter row than the one above means that day popped some waiting days.

Worked example

Days until warmer for [68, 71, 65, 64, 70, 66, 72]:

The waits are 1, 5, 2, 1, 2, 1, 0; the last day never finds a warmer one and stays at 0.

Largest rectangle for heights [3, 1, 4, 5, 3, 2, 1]. Each row is a pop, with its widest rectangle:

The largest area is 9, the rectangle of height 3 over bars 2 to 4.

Window maximum for [4, 2, 12, 3, 8, 1, 6] with k = 3. The deque shows values, front first:

The window maxima are 12, 12, 12, 8, 8.

Implementation

from collections import deque


def days_until_warmer(temps):
    waits = [0] * len(temps)
    stack = []                                   # indices, temperatures decreasing
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            waits[j] = i - j
        stack.append(i)
    return waits


def largest_rectangle(heights):
    best = 0
    stack = []                                   # indices, heights increasing
    for i, h in enumerate(heights + [0]):        # the 0 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


def window_maxima(nums, k):
    window = deque()                             # indices, values decreasing
    out = []
    for i, x in enumerate(nums):
        while window and nums[window[-1]] <= x:
            window.pop()
        window.append(i)
        if window[0] <= i - k:
            window.popleft()
        if i >= k - 1:
            out.append(nums[window[0]])
    return out

In largest_rectangle, heights + [0] makes the index i run one past the end, but heights[stack[-1]] only reads real bars, because the sentinel index itself is never read.

Variations and edge cases

• Strict versus non-strict comparison. Pop on < or <= depending on whether equal values count as "greater". For the rectangle the >= version is right: equal bars merge into a single rectangle when the later one is popped.
• Both neighbours at once. The popping step knows the next smaller on the right (the arrival) and the previous smaller on the left (the new top). Sum-of-subarray-minimums problems use both.
• Circular arrays. Run the loop over 2n indices, taking values modulo n, and only push on the first lap.
• Stack of pairs. The stock span stores (price, span) and merges a popped item's span into the arrival; no index arithmetic is needed.
• Sorted first. Car fleets sort by position, then a stack of arrival times drops any car that would catch the one ahead.
• Edge cases: an empty array, a strictly increasing input (everything pops at the end or immediately, depending on direction), all equal values, a window larger than the array, k = 1, and forgetting to expire the deque's front.

Complexity and tradeoffs

• Time: O(n): each index is pushed once and popped at most once, so the nested while amortises to constant time per item.
• Space: O(n) for the stack or deque.
• Baseline. Scanning forward from each item is O(n²); a heap-based window maximum is O(n log k); the deque is O(n).
• When it fails. The pattern answers questions about nearest items by order (next greater, previous smaller). If you need the k-th greatest or an arbitrary range's maximum, use a heap, a sparse table or a segment tree.

Problems

The home problems are the four canonical shapes: next-greater (daily temperatures), span (online stock span), area (histogram), and the deque (window maximum), plus car fleets, where the stack comes after a sort. Trapping rain water is listed as "also uses": its two-pointer solution is shorter, but the stack version is the same idea as the histogram.

Medium

• 739. Daily Temperatures Grind 169 NeetCode 150 NeetCode 250
  Keep indices of days still waiting for a warmer day on a decreasing stack, and resolve them when a warmer day arrives.
• 853. Car Fleet NeetCode 150 NeetCode 250
  Sort cars by position from the front, compute each one's arrival time, and a car joins the fleet ahead whenever it would arrive no later.
• 901. Online Stock Span NeetCode 250
  Keep price and span pairs on a decreasing stack, folding smaller prices' spans into the new price's span.

Hard

• 84. Largest Rectangle in Histogram Grind 169 NeetCode 150 NeetCode 250
  Keep bar indices with increasing heights; when a shorter bar arrives, each popped bar's widest rectangle ends right there.
• 239. Sliding Window Maximum Grind 169 NeetCode 150 NeetCode 250
  Keep a deque of indices with decreasing values, dropping indices that leave the window, so the front is always the window maximum.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 42. Trapping Rain Water Hard

Connections

This is the stack page with an ordering rule, and the deque is the structure the fixed-size window page said it would need for maxima. The rectangle trick returns in matrix problems that reduce each row to a histogram, and the sort-then-stack shape of car fleets is a greedy argument.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms: the aggregate analysis of stack operations, which gives the amortised O(n) bound.
• Berkman, Schieber and Vishkin, "Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values" (1993): the all-nearest-smaller-values problem this page solves.
• Vuillemin, "A unifying look at data structures" (1980), which introduced the Cartesian tree; the monotonic stack builds it in linear time.
• Sedgewick and Wayne, Algorithms, section 1.3 (bags, queues and stacks): the array-backed stack this pattern keeps.
• Skiena, The Algorithm Design Manual: the discussion of stacks and of scanning problems that avoid nested loops.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.