Stacks & Queues

Monotonic Stack

Keep a stack in sorted order to find the next greater/smaller element for all items in O(n).

Medium, about 90 minutes to practise.

1Understand

The idea

Keep the stack in sorted order. When a new element arrives, pop every element it "beats": the new element is the next greater (or smaller) one for each popped item. Each element is pushed and popped once, so the next-greater answer for every position takes O(n) in total.

Intuition

Keep the stack in sorted order (strictly increasing or decreasing by value). When a new element arrives, pop every element it "beats": the newcomer is the next greater (or smaller) for each popped item.

Each element is pushed and popped at most once, so answers for every position take O(n) total, far better than a nested scan.

Store indices when you need distances or to write into an answer array; store values when only the value matters.

What you will be able to do

  • Choose increasing vs decreasing order
  • Store indices rather than values

When to use it

  • Next greater / smaller element
  • Days until a warmer temperature
  • Largest rectangle, span or visibility

2See it

Walkthrough

Next greater element

a = [2, 1, 2, 4], decreasing stack of indices; pop when a new greater arrives.

1 / 4

i
2
1
2
4
0123
i → index 0

Push index 0. Stack holds indices with decreasing values: [0].

stack.append(i)

Live template

Line 5 active

1stack = [] # indices, values decreasing
2for i, x in enumerate(a):
3 while stack and a[stack[-1]] < x:
4 j = stack.pop(); answer[j] = i - j
5 stack.append(i)

Complexity: time O(n), space O(n)

O(n) time and O(n) space. Brute force is O(n²). Monotonic stacks also solve daily temperatures, largest rectangle in histogram, and sum of subarray minimums, same pop-when-beaten idea with a different answer update.

Read the walkthrough as text

Next greater element. nums = [2, 1, 2, 4, 3].

  1. Stack holds indices of a decreasing sequence. Answer starts as [-1,-1,-1,-1,-1].
  2. At 4 (index 3): it beats 2, 1, 2, pop those indices and set their answers to 4.
  3. Push 3. End of array: leftovers stay -1.
  4. Result: [4, 2, 4, -1, -1].

The stack always keeps candidates still waiting for a greater element to their right.

3Recognise it

Kinds of problems (8)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Next greater element

    Example. For each i, index of next element to the right that is greater.

    How. Increasing stack of indices; when x beats stack top, pop and assign answer.

  • Previous smaller element

    Example. Nearest smaller to the left for each position.

    How. Scan left to right with decreasing stack; pops see the current element as their answer.

  • Largest rectangle in histogram

    Example. Max area rectangle under a histogram.

    How. When popping height h, width uses distance to new stack top and current index.

  • Circular arrays (iterate twice)

    Example. Next greater in a circular array.

    How. Run the same stack loop for 2n indices with i % n.

  • Remove digits for smallest number

    Example. Remove k digits to leave the smallest number.

    How. Monotonic increasing stack of digits; pop while top > next and removals remain.

  • Scan from the right with a running candidate (132 pattern)

    Example. Does the array contain a 132 pattern?

    How. Track max so far from the right; stack of middles compares with left candidates.

  • Contribution of each element (sum of subarray minimums)

    Example. Sum of minimums of all subarrays.

    How. For each element, find previous/next smaller; contribution is val × left span × right span.

  • Maximal rectangle in a binary matrix

    Example. Largest rectangle of 1s in a 0/1 matrix.

    How. Each row is a histogram height; run largest-rectangle stack per row.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Values instead of indices

    Why it happens. Storing values on the stack feels natural when comparing heights.

    How it fails. Stack holds heights only, you cannot compute distance i, j when answering next greater.

    Fix. Push indices; compare via a[stack[-1]] and use index arithmetic for spans.

  • Wrong order

    Why it happens. Next greater vs next smaller use opposite comparison directions.

    How it fails. Next greater uses increasing stack but you pop while top > x, nothing ever pops.

    Fix. Next greater: pop while stack value < current (decreasing stack). Next smaller: reverse the comparison.

  • Remaining items unresolved

    Why it happens. The pass ends without assigning defaults for indices still on the stack.

    How it fails. Decreasing array, stack never emptied; answer arrays stay −1 even where problem defines default.

    Fix. After the scan, pop remaining indices and set answer per spec (e.g. −1 or distance to sentinel).

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons