cf.completefrontend
STACKS & QUEUES · CORE

Monotonic stack

Keep a stack whose values only go down (or only go up), so each new item instantly finds the items it beats.

Time O(n)Space O(n)11 practice problemsStep-through picture

The idea

Many questions ask, for each item in a list, about the next item to its right that is bigger (or smaller). Checking every later item for every item takes O(n^2) time. A monotonic stack answers all of them in one pass.

The stack holds the indexes of items that are still waiting for their answer. It is kept in decreasing order of value from bottom to top. When a new item arrives, every waiting item smaller than it has just found its next bigger item, so they are popped and answered. Then the new item is pushed and waits too.

"Monotonic" means the values on the stack only move in one direction. Flip the comparison and the same loop finds the next smaller item, or keeps an increasing stack instead.

An everyday example

People in a line looking for someone taller

People walk into a hall one at a time and stand in a line. Each person wants to know who is the first taller person to arrive after them. When a tall person walks in, everyone shorter at the end of the line sees them, writes down their name, and leaves. The people still waiting are always in order from tallest to shortest, because anyone shorter behind a taller person would already have left.

How the example maps to the code
In the exampleIn the code
People still waitingthe indexes on stack
A new person walks innums[i]
Shorter people at the end see them and leavewhile (nums[stack[stack.length - 1]] < nums[i]) stack.pop()
Writing down the taller person's heightanswer[j] = nums[i]
Nobody taller ever camethe default -1

From the slow way to monotonic stack

  1. Start with the obvious way to find, for each item, the next bigger item to its right: from every index i, scan right until something bigger turns up. On a list that only goes down, like 9, 8, 7, 6, every scan runs to the end, so the total is about n^2 / 2 comparisons.
  2. Turn the question around. Instead of each item searching forward, let each new item answer the items that are still waiting. When nums[i] arrives, it is the answer for every earlier item that is smaller than it and has no answer yet. So keep the waiting items in a list and let each new item settle as many of them as it can.
  3. Which items are waiting? Never a smaller item to the left of a bigger waiting one: the bigger item, when it arrived, would have answered it. So the waiting values only go down from oldest to newest. That means the items a new value can answer are always a run at the newest end: the smallest, most recent ones.
  4. A list where you only touch the newest end is a stack. Pop while the top's value is smaller than nums[i], record nums[i] as each popped item's answer, then push i. Each index goes on once and comes off at most once. That loop is the monotonic stack.

How it works

  1. Fill answer with -1, meaning "no bigger item found yet", and start with an empty stack of indexes.
  2. Walk i from left to right.
  3. While the stack isn't empty and the value at the top index is smaller than nums[i], pop that index j.
  4. Each popped j has found its answer: answer[j] = nums[i].
  5. Push i. It now waits for a bigger item of its own.
  6. Indexes still on the stack at the end never found a bigger item, so they keep -1.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function nextGreater(nums) {
  2. const answer = new Array(nums.length).fill(-1);
  3. const stack = [];
  4. for (let i = 0; i < nums.length; i++) {
  5. while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
  6. const j = stack.pop();
  7. answer[j] = nums[i];
  8. }
  9. stack.push(i);
  10. }
  11. return answer;
  12. }

How fast it is

TimeO(n)
Extra memoryO(n)

Each index is pushed once and popped at most once, so all the inner loops together run at most n times. The stack can hold all n indexes when the values only go down.

  • Best caseO(n)

    Values that only go up, like 1, 2, 3, 4. Each new item pops the one before it, so the stack never holds more than one index.

  • Average caseO(n)

    Mixed values. Some steps pop nothing and some pop several, but the pops add up to at most n.

  • Worst caseO(n)

    Values that go down and then one big value, like 6, 5, 4, 3, 9. The last step pops 4 indexes at once, but that is still only n - 1 pops in total.

Common mistakes

  • Pushing values instead of indexes, then having no way to know which answer slot to fill or how far apart two items are.
  • Using <= when the task wants strictly greater, which pops equal values too early. Decide how ties should behave and pick < or <= on purpose.
  • Writing an if instead of a while, so only one waiting item is answered per new item.
  • Thinking the nested loops make it O(n^2) and avoiding it. Each index is popped at most once.

When to use it

Look for these clues in a problem:

  • For each item, the task asks for the next (or previous) item that is greater or smaller.
  • The task asks how far each item can extend left or right before something taller or shorter blocks it.
  • You want the largest rectangle, span, or window bounded by the smallest or biggest value.
  • A brute force would scan right from every item, and the input is large.

Check yourself

Answer each one in your head first, then open it.

Why does the stack hold indexes instead of values?

A popped item needs to know which answer slot to fill, and distance questions need i - j. A value alone can't tell you its position.

If the inner loop can pop many items, why is the whole thing O(n)?

Each index is pushed exactly once and can be popped at most once. So across the whole run there are at most n pops, however they are grouped.

On [4, 7, 3, 3, 8, 1, 6], why does the first 3 get 8 and not the second 3?

The answer must be strictly greater. 3 < 3 is false, so the second 3 doesn't pop the first one, and both wait until 8 arrives.

What would an if instead of the while break?

Each new item would answer at most one waiting item. In the trace, 8 would answer only index 3, and indexes 1 and 2 would end with -1 instead of 8.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 11 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps two rules at the top of each loop. First, the stack holds exactly the indexes before i that have no answer yet. Second, their values never go up from bottom to top. Both hold at the start, when the stack is empty.

When nums[i] arrives, the waiting values smaller than it form a run at the top, because of the second rule. For each popped j, nums[i] is the first bigger value to its right: any bigger value between j and i would already have popped j, and j was still waiting. The while stops at a value that is at least nums[i], so pushing i keeps the values from going up, and both rules hold again.

The loop ends after the last index. By the first rule, the indexes left on the stack never met a bigger value to their right, so their -1 is correct. The run time is O(n) because each index is pushed once and popped at most once, so all the inner while loops together pop at most n times.

Going deeper

3 more ideas

Why the stack stays in decreasing order

Before pushing i, the loop pops every index whose value is smaller than nums[i]. So right after the push, the value below i is at least nums[i]. That holds for every push, so the values from bottom to top never increase. This is also why the top is always the first item to be answered: it is the smallest waiting value.

Why it is O(n) even with a loop inside a loop

The inner while can pop many items at once, but each index is pushed exactly once and popped at most once over the whole run. So the total number of pops is at most n, and the whole algorithm does O(n) work. This kind of counting, total work spread over all steps, is called amortized analysis.

Variations

Use > instead of < to find the next smaller item. Walk from right to left, or read the top before pushing, to get the previous greater item. Store indexes rather than values so you can compute distances such as "how many days until a warmer day" with i - j. For a circular list, walk the indexes twice using i % n.

Work it by hand

Every step in a table, with why

Find the next greater value for seven numbers, including two equal 3s next to each other and a big value that settles three waiting items at once.

nums = [4, 7, 3, 3, 8, 1, 6]

Stepinums[i]Popped and answeredstack values (bottom to top)answerWhy
104none4[-1, -1, -1, -1, -1, -1, -1]The stack is empty, so 4 just starts waiting.
217index 0 gets 77[7, -1, -1, -1, -1, -1, -1]4 < 7, so 7 is the first bigger value to the right of index 0.
323none7, 3[7, -1, -1, -1, -1, -1, -1]7 is not smaller than 3, so nothing pops. 3 waits on top of 7.
433none7, 3, 3[7, -1, -1, -1, -1, -1, -1]A tie: 3 < 3 is false, so the first 3 keeps waiting. An equal value is not greater.
548indexes 3, 2, 1 get 88[7, 8, 8, 8, -1, -1, -1]8 beats 3, 3, and 7, so the while pops three times in one step. The stack had only smaller values below.
651none8, 1[7, 8, 8, 8, -1, -1, -1]1 is smaller than 8, so it waits.
766index 5 gets 68, 6[7, 8, 8, 8, -1, 6, -1]6 beats 1 but not 8, so the while stops after one pop.

It returns [7, 8, 8, 8, -1, 6, -1]. The loop made 7 pushes and 5 pops. Indexes 4 and 6 are still on the stack at the end, so they keep -1.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Monotonic stackO(n)O(n)For every item you need the nearest bigger or smaller item on one side, on large input.
Scan right from every itemO(n²)O(1)The list is tiny, or you only need the answer for one or two items.
Monotonic dequeO(n)O(k)You need the biggest value inside a moving window of size k, not the next bigger value.

Extra memory: O(n): the answer array, plus a stack that holds every index when the values only go down. On 6, 5, 4, 3, 9 it reaches 4 indexes before the 9 arrives.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Monotonic stack and the other approaches, on a scale where each line up is 10 times more steps.
  • Monotonic stack, Monotonic deque O(n)
  • Scan right from every item O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Monotonic stack101,0001 million
Scan right from every item1001 million1 trillion
Monotonic deque101,0001 million

Inputs that need care

5 tricky inputs
An empty list: nums = []
The loop never runs and the function returns [].
All values equal: [5, 5, 5]
5 < 5 is false, so nothing ever pops and every answer stays -1. If equal values should count, use <=.
Values that only go down: [9, 6, 2]
Nothing pops, the stack grows to hold every index, and every answer is -1.
Negative numbers: [-3, -8, -1]
The answer is [-1, -1, -1], but the first two -1s are real answers: -1 is the next greater value after -3 and after -8. Only the last one means "none". When -1 can be a real value, fill answer with null instead.
A circular list, where the search wraps past the end
Loop i from 0 to 2n - 1 and use nums[i % n], pushing only during the first pass. Items waiting at the end get a second chance at the values from the start.

Variations and follow-ups

Twists interviewers add

Next smaller instead of next greater

Flip the comparison to nums[stack[stack.length - 1]] > nums[i]. The stack's values then go up from bottom to top, and each pop records the first smaller value to the right.

Previous greater

Before pushing i, the item left on top (after the pops) is the nearest earlier value that is bigger than or equal to nums[i]. Record it then, and the same single loop answers the leftward question.

Distances instead of values

Store i - j in answer[j] instead of nums[i]. This answers "how many steps until a bigger value", such as days until a warmer day, which is why the stack holds indexes.

Largest rectangle under a bar chart

For each bar, the widest rectangle of that height stops at the nearest shorter bar on each side. An increasing stack finds both sides in one pass: when a bar pops, the new item is its right limit and the item below it is its left limit.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "next greater", "next smaller", "previous", "how many days until", "how far can it see", or "largest rectangle". The question names a direction and a comparison for every item.
  • Say the rule out loud: "the stack holds the items still waiting for an answer, and their values only go down, so a new item answers a run at the top". Then explain why it is O(n): each index is pushed once and popped once.
  • Test by hand on a list that only goes up, one that only goes down, and one with equal neighbors. They check the pops, the leftover -1s, and the choice between < and <=.
  • Expect the follow-up "what if the list is circular?". Walk i over 2n steps with i % n, and push only in the first pass.

Where frontend code uses it

The same idea in real UI code
  • Chart widgets that label each point with "days until a higher value" (stock, traffic, or price charts) compute it with a monotonic stack.
  • Finding the largest empty rectangle in a grid, such as free space for placing a widget on a dashboard layout, uses the histogram method, which is built on a monotonic stack.
  • Deciding how far a bar's tooltip or label can extend before a taller bar blocks it is the "next greater element" question.

Related algorithms