Monotonic stacks and queues

The "next greater" family

Many problems ask, for every item, about the nearest item to its right (or left) that is bigger or smaller: the next warmer day, the next higher price, the previous taller building. Checking all later items for every item is O(n²). A monotonic stack answers all of them in one O(n) pass.

Monotonic means "always moving in one direction". A monotonic stack keeps its items sorted from bottom to top, for example in decreasing order. Before pushing a new item, it pops every item that would break the order. Those popped items have just met their answer.

Next greater element

Walk left to right and keep a stack of INDEXES whose next greater value is not known yet. Their values never increase from bottom to top, because a bigger arrival would already have popped them. When x arrives, every waiting index with a value smaller than x has found its next greater element: x. Pop those and record x, then push the current index. Whatever is left on the stack at the end has nothing greater to its right, so its answer is −1.

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                       # indexes still waiting for an answer
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

print(next_greater([2, 1, 2, 4, 3]))   # Output: [4, 2, 4, -1, -1]

Why it is O(n)

Each index is pushed once and popped at most once, so the inner while loop runs at most n times over the WHOLE walk, not n times per item. That makes it O(n) time, with O(n) space for the stack and the result. This is the same amortised argument as the variable sliding window in Module 3.

Daily temperatures and stock span

Daily temperatures asks, for each day, how many days you must wait for a warmer one (0 if never). It is the next greater element again, but when index j is popped at day i you record the distance i − j instead of the value.

Stock span asks, for each day, how many consecutive days up to and including today had a price less than or equal to today's. This looks to the LEFT. Keep a stack of (price, span) pairs with strictly decreasing prices. A new price pops every pair whose price is less than or equal to it and adds their spans to its own span of 1. The example below shows it in code.

Sliding window maximum with a monotonic deque

For every window of size k, report its maximum. Rescanning each window is O(n × k), and a heap gives O(n log n). A monotonic deque gives O(n). Keep a deque of indexes whose values decrease from front to back; the front is then always the maximum of the current window. For each index i:

1. Pop from the BACK every index whose value is ≤ nums[i]. They can never be a window maximum again: nums[i] is at least as big and stays in the window longer.
2. Append i at the back.
3. If the front index has slid out of the window (front ≤ i − k), pop it from the FRONT.
4. Once i ≥ k − 1 the first window is complete; from then on its maximum is nums[front].

The trace is for nums = [1, 3, −1, −3, 5, 3, 6, 7] with k = 3, giving [3, 3, 5, 5, 6, 7]. Every index enters and leaves the deque at most once: O(n) time and O(k) space.

Choosing the direction and the comparison

• Next greater: keep values decreasing and pop while top < x. Next smaller: keep values increasing and pop while top > x.
• Store indexes, not values, when you need distances or must know whether an item has left a window.
• With duplicates, decide between < and <=. For "strictly greater", equal values must keep waiting, so pop only on <.

Common mistakes

• Storing values instead of indexes, then being unable to compute distances. Fix: push indexes and read nums[index].
• The wrong comparison with duplicates. Fix: write down the rule ("strictly greater") and test [3, 3, 3].
• Forgetting the items still on the stack at the end. Fix: fill the result with the "no answer" value (−1 or 0) before the loop.
• In window maximum, forgetting to drop the expired front index. Fix: pop from the front when front ≤ i − k.
• Believing the nested while makes it O(n²). Fix: count pushes and pops; there are at most n of each.