Monotonic stack / queue

intermediateCommon atGoogleAmazonMicrosoftUberCitadelRead firstStacksQueues and dequesSliding windowPractise in the Sandbox →

A monotonic stack keeps its values in sorted order by popping anything the new element “beats” before pushing it. The pops are exactly the moments an element meets its next greater (or smaller) neighbour. A monotonic deque does the same but also drops expired items from the front, giving the max or min of every sliding window. Each element is pushed and popped once: O(n) total.

The idea in plain words

Stand at the end of a street of buildings and look left. You can only see the buildings that are taller than everything between them and you. A short building hidden behind a tall one will never be visible from anywhere further right either. So you can forget it.

That’s the whole insight: once an element is dominated, it’s useless forever. A monotonic stack throws dominated elements away the moment they become useless, so what remains is always sorted, and the useful candidate is always on top.

• For “next greater to the right”: the stack holds elements still waiting for a bigger value. They’re in decreasing order (a bigger one would have resolved the smaller ones below it). When a new value arrives, it resolves every waiting value smaller than it.
• For “previous greater to the left”: same scan, but you read the answer from the top after popping.

Brute force asks each element “scan right until you find someone bigger”: O(n²) for a decreasing-then-spike input. The stack does all of those scans in one pass.

See it

The bars are the “buildings”. Yellow ones are waiting on the stack. Watch a tall value arrive and resolve several waiting ones in a burst, then notice the stack values always read in decreasing order.

Next greater element with a decreasing stack

step through

values

2

7

3

5

4

6

8

1

2

7

3

5

4

6

8

1

01234567

input

·

·

·

·

·

·

·

·

next greater (· = still waiting)

stack[]

stack values[]

pops0

currentwaiting on the stackjust resolvedresolved

The stack holds indices still waiting for a bigger value to their right. Their values only decrease from bottom to top.

↺◀▶ Play▶1 / 24

When to reach for it

The problem says…	Why a monotonic structure fits
“next greater / next smaller element”, “how many days until a warmer day”	The pop is the answer.
“previous greater / smaller”, “span”, “how far back until…”	After popping, the top is the nearest dominating element.
“max / min of every window of size k”	A monotonic deque: drop dominated items at the back, expired items at the front.
“largest rectangle”, “sum over all subarrays of their min”	Each element’s reach left and right is its previous/next smaller.
a brute force that scans outward from every element until a bigger/smaller one	That scan is what the stack shares across elements.

How it works

Monotonic stack (next greater)

1. Fill the answer with a default (-1: nobody bigger).
2. For each index i: while the top’s value is smaller than a[i], pop it and record a[i] as its answer.
3. Push i. The stack’s values stay decreasing from bottom to top.
4. Whatever remains at the end never found a bigger value and keeps the default.

Python

next_greater.py

def next_greater(a: list[int]) -> list[int]:
    """For each a[i], the first value to its right that is strictly bigger, or -1."""
    ans = [-1] * len(a)  # 1. default: nobody bigger shows up
    stack: list[int] = []  # 2. indices still waiting; their values decrease bottom -> top
    for i, x in enumerate(a):
        while stack and a[stack[-1]] < x:  # 3. x resolves every smaller waiting index
            ans[stack.pop()] = x
        stack.append(i)  # 4. x now waits for its own answer
    return ans


if __name__ == "__main__":
    assert next_greater([2, 7, 3, 5, 4, 6, 8, 1]) == [7, 8, 5, 6, 6, 8, -1, -1]
    assert next_greater([5, 4, 3]) == [-1, -1, -1]
    assert next_greater([1, 1, 2]) == [2, 2, -1]  # strictly bigger: equal values keep waiting
    assert next_greater([]) == []
    print("ok")

TypeScript

next_greater.ts

import assert from "node:assert/strict";

/** For each a[i], the first value to its right that is strictly bigger, or -1. */
export function nextGreater(a: number[]): number[] {
  const ans = new Array<number>(a.length).fill(-1); // 1. default: nobody bigger shows up
  const stack: number[] = []; // 2. indices still waiting; values decrease bottom -> top
  for (let i = 0; i < a.length; i++) {
    while (stack.length > 0 && a[stack[stack.length - 1]] < a[i]) {
      ans[stack.pop()!] = a[i]; // 3. a[i] resolves every smaller waiting index
    }
    stack.push(i); // 4. a[i] now waits for its own answer
  }
  return ans;
}

assert.deepEqual(nextGreater([2, 7, 3, 5, 4, 6, 8, 1]), [7, 8, 5, 6, 6, 8, -1, -1]);
assert.deepEqual(nextGreater([5, 4, 3]), [-1, -1, -1]);
assert.deepEqual(nextGreater([1, 1, 2]), [2, 2, -1]); // strictly bigger: equal values keep waiting
assert.deepEqual(nextGreater([]), []);
console.log("ok");

C#

next_greater.cs

// For each a[i], the first value to its right that is strictly bigger, or -1.
static int[] NextGreater(int[] a)
{
    var ans = new int[a.Length];
    Array.Fill(ans, -1);                    // 1. default: nobody bigger shows up
    var stack = new Stack<int>();           // 2. indices still waiting; values decrease bottom -> top
    for (int i = 0; i < a.Length; i++)
    {
        while (stack.Count > 0 && a[stack.Peek()] < a[i])
            ans[stack.Pop()] = a[i];        // 3. a[i] resolves every smaller waiting index
        stack.Push(i);                      // 4. a[i] now waits for its own answer
    }
    return ans;
}

if (!NextGreater([2, 7, 3, 5, 4, 6, 8, 1]).SequenceEqual([7, 8, 5, 6, 6, 8, -1, -1])) throw new Exception("case 1");
if (!NextGreater([5, 4, 3]).SequenceEqual([-1, -1, -1])) throw new Exception("case 2");
if (!NextGreater([1, 1, 2]).SequenceEqual([2, 2, -1])) throw new Exception("strictly bigger");
if (NextGreater([]).Length != 0) throw new Exception("empty");
Console.WriteLine("ok");

Store indices, not values: you need to know where to write the answer, and indices also give distances (i - j) for “how many days until” questions.

Monotonic stack (previous greater, read after popping)

The same loop, with the answer read from what’s left on the stack.

Python

spans.py

def spans(prices: list[int]) -> list[int]:
    """Span of day i: how many consecutive days ending at i had price <= prices[i]."""
    out: list[int] = []
    stack: list[int] = []  # 1. indices of a strictly decreasing run of prices (bottom -> top)
    for i, p in enumerate(prices):
        while stack and prices[stack[-1]] <= p:  # 2. smaller-or-equal days are covered by today
            stack.pop()
        # 3. the top is now the previous strictly greater day (or none)
        out.append(i - stack[-1] if stack else i + 1)
        stack.append(i)
    return out


if __name__ == "__main__":
    assert spans([100, 80, 60, 70, 60, 75, 85]) == [1, 1, 1, 2, 1, 4, 6]
    assert spans([1, 2, 3]) == [1, 2, 3]
    assert spans([3, 3, 3]) == [1, 2, 3]
    assert spans([]) == []
    print("ok")

TypeScript

spans.ts

import assert from "node:assert/strict";

/** Span of day i: how many consecutive days ending at i had price <= prices[i]. */
export function spans(prices: number[]): number[] {
  const out: number[] = [];
  const stack: number[] = []; // 1. indices of a strictly decreasing run of prices (bottom -> top)
  prices.forEach((p, i) => {
    while (stack.length > 0 && prices[stack[stack.length - 1]] <= p) stack.pop(); // 2. covered by today
    // 3. the top is now the previous strictly greater day (or none)
    out.push(stack.length > 0 ? i - stack[stack.length - 1] : i + 1);
    stack.push(i);
  });
  return out;
}

assert.deepEqual(spans([100, 80, 60, 70, 60, 75, 85]), [1, 1, 1, 2, 1, 4, 6]);
assert.deepEqual(spans([1, 2, 3]), [1, 2, 3]);
assert.deepEqual(spans([3, 3, 3]), [1, 2, 3]);
assert.deepEqual(spans([]), []);
console.log("ok");

C#

spans.cs

// Span of day i: how many consecutive days ending at i had price <= prices[i].
static int[] Spans(int[] prices)
{
    var output = new int[prices.Length];
    var stack = new Stack<int>();       // 1. indices of a strictly decreasing run of prices
    for (int i = 0; i < prices.Length; i++)
    {
        while (stack.Count > 0 && prices[stack.Peek()] <= prices[i])
            stack.Pop();                // 2. smaller-or-equal days are covered by today
        // 3. the top is now the previous strictly greater day (or none)
        output[i] = stack.Count > 0 ? i - stack.Peek() : i + 1;
        stack.Push(i);
    }
    return output;
}

if (!Spans([100, 80, 60, 70, 60, 75, 85]).SequenceEqual([1, 1, 1, 2, 1, 4, 6])) throw new Exception("case 1");
if (!Spans([1, 2, 3]).SequenceEqual([1, 2, 3])) throw new Exception("case 2");
if (!Spans([3, 3, 3]).SequenceEqual([1, 2, 3])) throw new Exception("ties");
if (Spans([]).Length != 0) throw new Exception("empty");
Console.WriteLine("ok");

Monotonic deque (max of a sliding window)

A window both gains an element on the right and loses one on the left. A stack can’t lose from the bottom, so use a deque:

1. Keep a deque of indices whose values decrease from front to back.
2. Before adding index i, pop from the back every index whose value is ≤ a[i]. They are older and not bigger, so they can never be a window max again.
3. Push i on the back.
4. If the front index has slid out of the window (front ≤ i − k), pop it from the front.
5. Once the window is full, the front is its maximum.

Step through it, and try a large k to see that the deque stays small:

Sliding window maximum with a monotonic deque

step through

valueswindow k

1

3

-1

-3

5

3

6

7

2

012345678

·

deque, front → back (indices [])

·

window maxima

window—

deque size0

current windowfront = current maxin deque (a future max)just removed

The deque holds indices that could still become a window max, values decreasing front → back. The front is always the current max.

↺◀▶ Play▶1 / 25

Which direction, strict or not?

Four knobs decide every variant: greater or smaller, next or previous, strict or non-strict (< vs <= in the pop condition), and what you store (index, value, or a pair). Say them out loud before coding. Duplicates are where strictness bites: in the sample above [1, 1, 2] → [2, 2, -1] because equal values keep waiting under a strict <.

What it costs

	Time	Space
brute force (scan outward from each element)	O(n²) worst	O(1)
brute force window max	O(n·k)	O(1)
monotonic stack	O(n)	O(n) worst (strictly decreasing input)
monotonic deque, window max	O(n), independent of k	O(k)
heap for window max (lazy deletion)	O(n log n)	O(n)

The amortized argument: every index is pushed once and popped at most once. The inner while loops, summed over the whole scan, run at most n times. So O(n), even though one step can pop many.

Variations you’ll meet

• Increasing vs decreasing. Next smaller uses an increasing stack (pop while the top is bigger).
• Right-to-left scan. Scan from the end to get “next greater” by reading the top after popping, like the span example.
• Both sides at once. When an element is popped by i, then i is its next smaller and the new top is its previous smaller. Largest-rectangle-in-histogram uses exactly this.
• Circular arrays. Walk the array twice (i % n) so elements near the end can find answers near the start.
• Window min. Flip the comparison: keep values increasing front to back.
• Stack of pairs for streams. For an online “span” query, push (value, span) and merge popped spans into the new one, so you don’t need the whole history.

Pitfalls

• Wrong strictness with duplicates. Decide whether “greater” means > or ≥, and match < vs <= in the pop condition.
• Storing values when you need indices. You can’t write the answer back or measure distance without the index.
• Forgetting leftovers. Elements still on the stack at the end need the default answer.
• Using a list as a deque. Python list.pop(0) and JS shift() are O(n), which silently makes the window version O(n·k). Use collections.deque, a head index, or a ring buffer.
• Evicting by value instead of index in the window deque. Duplicates make value-based eviction remove the wrong copy.

In the interview

• Start from the brute force: “For each element I scan right until something bigger. The repeated scans overlap; an element hidden behind a bigger one can never be anyone’s answer, so I can discard it.”
• Name the invariant: “The stack holds indices of unresolved elements, values decreasing bottom to top.”
• Give the O(n) amortized argument (push once, pop once).
• Expect follow-ups: duplicates, circular input, “now the min too”, “now the input is a stream” (the deque works online), “now the window is time-based” (evict by timestamp instead of index).

Check yourself

Check yourself

pick one

In next-greater with a stack, why can a popped index be discarded forever?

ABecause its answer is now known, so it has no further roleBBecause it is bigger than everything after itCBecause the stack has limited capacity

Check yourself

pick one

In the window-max deque, a new value 5 arrives and the back of the deque holds a value 5 from an earlier index. Should you pop it?

ANo, it is equal, not smallerBYes: it is older and not bigger, so the new 5 will outlive it and is at least as goodCOnly if the window is full

Check yourself

pick one

With k = n/2, how many deque operations does the window-max algorithm do in total?

AO(n·k) = O(n²)BO(n log n)CO(n)

Practice on your own

Classic textbook exercises, not gym questions:

• Days until a warmer temperature, for each day.
• Largest rectangle in a histogram.
• Trapping rain water (try it with a stack, then with two pointers).
• Sum of the minimums of all subarrays (each element’s contribution = left reach × right reach).

Go deeper

• cp-algorithms: Minimum stack / Minimum queue: the deque technique and the two-stack queue variant.
• Laaksonen, Competitive Programmer’s Handbook, §8.2 “Nearest smaller elements” and §8.3 “Sliding window minimum”.
• Python docs, collections.deque: O(1) appends and pops at both ends.

Related

StacksThe plain LIFO structure underneath.

Queues and dequesDouble-ended operations for the window version.

Sliding windowWhere the window max shows up.

HeapsThe O(n log n) alternative for window extremes.