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
Push index 0. Stack holds indices with decreasing values: [0].
Live template
Line 5 active
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].
- Stack holds indices of a decreasing sequence. Answer starts as
[-1,-1,-1,-1,-1]. - At
4(index 3): it beats2,1,2, pop those indices and set their answers to4. - Push
3. End of array: leftovers stay-1. - 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.