Next greater element

1 min 2 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Here are eight days of temperatures: 73, 74, 75, 71, 69, 72, 76, 73. For each day, how many days do you wait until a warmer one? Day 1 (73) waits 1 day for 74. Day 4 (71) waits 2 days for 72. Day 7 (76) never gets a warmer day, so the answer is 0.

By hand you would take each day and scan forward until you find something bigger. For day 1 that is one look, but for day 3 (75) it is four looks, and in the worst case, a list that keeps falling, every day scans all the way to the end and finds nothing. For n days that is up to 1 + 2 + … + (n − 1) looks.

1 + 2 + … + (n − 1) = n(n − 1) / 2

For 8 days that is 28 looks. For a million days it is about 500 billion. The waste is obvious: when day 3 scans past 71, 69 and 72, nobody remembers that those days are also still waiting, so each of them will scan the same stretch again.

Build the structure, one piece at a time

Turn the problem around. Instead of each day looking forward, let each new day look back at the days that are still waiting, and answer them. So we need a waiting list.

Piece 1: a pile. A stack is a pile of index cards. You can put a card on top (push) or take the top card off (pop), nothing else. We will put each day's index on the pile when it arrives.

Piece 2: a rule for the pile. When a new day arrives, compare it with the card on top. If the new day is warmer, the top day has just found its answer: pop it, and its answer is (today − that day). Keep popping while the new day beats the top. Then push today, because today is now waiting too.

Watch the pile on the example (we store indices, shown here with their temperatures):

Notice what the pile always looks like: 75, 71, 69 and later 75, 72. Reading from bottom to top the temperatures only go down. That is why it is called a monotonic (one-direction) stack, and it is not an accident.

Why it is correct

The invariant, in plain words: the pile holds exactly the days that are still waiting for a warmer day, and from bottom to top their temperatures decrease.

Why does it stay true? A day only leaves the pile when a warmer day arrives, so everything on the pile is still waiting. And a new day is pushed only after every smaller day above it has been popped, so the card under it is always warmer. Decreasing from bottom to top is preserved.

Now the key consequence. Suppose day j arrives and day i is on top of the pile with a smaller temperature. Could some day between i and j have been warmer than day i? No, because that day would have popped i when it arrived. So j really is the first warmer day after i, and the answer j − i is exact. Days left on the pile at the end never met a warmer day, so their answer is 0.

Why it is fast

Count the pile operations instead of the loop iterations. Each day is pushed exactly once. A day can be popped at most once, because once it is gone it never comes back. So the total number of pushes and pops is at most 2n.

pushes + pops ≤ n + n = 2n, so the running time is O(n)

The inner while loop looks like it could be expensive, but it only runs when it pops something, and the pops are already counted. For a million days that is at most two million pile moves instead of 500 billion comparisons.

How to recognise it in an interview

Listen for "next greater", "next warmer", "how many days until", "first element to the right that is bigger", or the mirror image "previous smaller". Any question that asks, for every position, about the nearest position in one direction that beats it is this pattern. Say out loud: "Each element waits on a stack until something bigger arrives, so every element is pushed once and popped once."

Daily Temperatures is the pattern exactly as above. Online Stock Span asks how many days back the price was lower or equal, which is the same stack scanned for previous greater instead of next greater. Number of Visible People in a Queue is the same pile walked from the right, counting how many pops each new person causes.

02The idea in one line

Keep a decreasing stack; a bigger newcomer resolves everything smaller on top.

Reach for it when: Next greater/warmer day, stock span, 'how many until bigger'.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Daily Temperatures on [73,74,75,71,69,72,76,73]. These are its captions in order, so you can follow without the video or check a step you missed.

1. A decreasing stack of indices still waiting for a warmer day
2. Push index 0 (73): it is now waiting for a warmer day
3. 74 > 73: pop index 0, answer[0] = 1 − 0 = 1
4. Then push index 1 (74)
5. 75 > 74: pop index 1, answer[1] = 2 − 1 = 1
6. Then push index 2 (75)
7. Push index 3 (71): it is now waiting for a warmer day
8. Push index 4 (69): it is now waiting for a warmer day
9. 72 > 69: pop index 4, answer[4] = 5 − 4 = 1
10. 72 > 71: pop index 3, answer[3] = 5 − 3 = 2
11. Then push index 5 (72)
12. 76 > 72: pop index 5, answer[5] = 6 − 5 = 1
13. 76 > 75: pop index 2, answer[2] = 6 − 2 = 4
14. Then push index 6 (76)
15. Push index 7 (73): it is now waiting for a warmer day
16. End: indices left on the stack never see a warmer day, answer stays 0
17. Each index is pushed once and popped at most once: O(n)

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Monotonic Stack: Largest rectangle (bounds by pops), Greedy removal with a stack, Previous and next smaller (both sides).