Next greater element and the monotonic stack

Why it matters

Many questions ask, for each item in a list, about the nearest item to its left or right that is bigger or smaller. How many days until a warmer day? How many days has this stock price been at its current level or lower? How wide is the widest rectangle that fits under a row of bars? Each question looks like a search for every item. A naive program searches again and again, and the work grows with the square of the list length. A monotonic stack answers all of them in one pass, with work that grows only in a straight line with the list. This lesson builds the idea from nothing, traces it step by step, and then applies it to five problems that interviewers like to ask.

The problem, and why the obvious answer is slow

Start with a plain question. You have an array of numbers. For each position i, find the first number to its right that is strictly greater than a[i]. If there is none, the answer is -1.

Take the array {4, 5, 2, 25}. The answer for 4 is 5, because 5 is the first number to its right that is bigger than 4. The answer for 5 is 25, because the 2 is too small and 25 is the first bigger number. The answer for 2 is 25. The answer for 25 is -1, because nothing to its right is bigger. So the answers are {5, 25, 25, -1}.

The simple method looks at each position and scans right until it finds a bigger number. For a list of n numbers, the scan from the first position may look at n - 1 numbers, the scan from the second at n - 2, and so on. The total is about n times n divided by 2, which is O(n squared). The notation means that the work grows with the square of the input size. Doubling the list makes the work four times larger. For a list of 100,000 numbers, that is about five billion comparisons, which is too slow for most time limits.

The question is whether the scans repeat work. They do. When the scan from position 1 passes over position 2, it has learned something about position 2. A smart method keeps that knowledge and uses it later, instead of starting over. A stack is the tool that remembers what is still waiting.

An everyday picture: people waiting in a line

Imagine people standing in a line, all facing right, and each one wants to know who is the first taller person ahead of them. Now a new person arrives at the right end of the line. Every person still waiting who is shorter than the new arrival can now see their answer: the new person is the first taller one they have met. Those people leave the waiting line, and the new person joins the line at the end.

The line of waiting people is a stack. The newest waiter is on top. A new arrival only needs to look at the top of the stack. If the top is shorter, that person gets their answer and leaves, and the next one down is checked. The process stops when the top is taller, or the stack is empty. Then the new person joins the stack.

Notice that the people still waiting are always in a specific order. From the bottom of the stack to the top, the heights go down. A waiting person near the top is shorter than the people below them, because anyone taller would already have stopped the shorter ones. A stack whose contents are always sorted in one direction is called a monotonic stack. Monotonic means "moving in one direction only", so a monotonic stack is always sorted, either increasing or decreasing from bottom to top.

The idea, precisely

For next greater, keep a stack of positions (indexes) that are still waiting for an answer. Keep the values in decreasing order from bottom to top. The algorithm walks through the array from left to right. For each new index i:

1. While the stack is not empty and the value at the top is smaller than a[i], the top has found its answer. Write a[i] as its answer, and pop it.
2. Push i. It is now waiting for a bigger value on its right.
3. When the walk ends, any index left on the stack has no bigger value to its right, so its answer stays -1.

Why store indexes and not values? Because the answer must be written back to the position it belongs to. When a bigger value arrives and pops a waiting entry, the code needs to know where to write the answer. The index tells it where. A stored value would tell you the number but not where it lives in the array. Indexes also let you compute distances, as you will see in the daily temperatures example.

The step-by-step trace below shows the stack state for {4, 5, 2, 25}. Read it carefully, because it is the core of the whole lesson.

Trace of the next-greater stack on 4 5 2 25, with each step showing the stack contents and the answer written

Step through the push and pop pattern below. The same moves appear in every problem in this lesson.

Worked trace, step by step

The final answers are 5 25 25 -1, which matches the definition. Notice that at step 3, a single new value caused two pops. This is the moment the stack does its work, and it is also why the total cost is small.

The code

The function below does the whole job. The main function prints two results. The output has no trailing space, because the helper function prints a space only between values.

Output:

5 25 25 -1
-1 12 12 -1

The second line is worth checking by hand. For {13, 7, 6, 12}, the 13 has nothing bigger to its right, so it gets -1. The 7 is followed by 6 and then 12, so its answer is 12. The 6 is followed by 12, so its answer is also 12. The last 12 has nothing to its right. The stack handles this without any special case, because the 7 and 6 stay on the stack until 12 arrives.

The function takes const vector<int>& a. The & means the function receives a reference to the caller's vector, not a copy. The const promises that the function will not change it. This is a good habit for read-only input, because copying a large array on every call would waste time and memory.

Why it is O(n)

The loop in the code has a while inside a for. That looks like a nested loop, which would suggest O(n squared). The correct count is different. Count how many times each kind of operation happens over the whole run.

Each index is pushed exactly once, when its turn comes in the outer loop. So there are exactly n pushes. Each index is popped at most once, because after it is popped it is gone for good. So there are at most n pops, across all the while loops together. The total work is at most 2n stack operations, plus n comparisons for the outer loop. That is O(n).

This style of argument is called amortised analysis. It spreads the cost of a rare expensive step across all the cheap steps. One while loop may pop ten items, but those ten items were each pushed earlier, and each push was counted once already. A single expensive step does not mean the average step is expensive.

The space is O(n) in the worst case, when the input is strictly decreasing and the stack holds everything at once. A decreasing list is the worst case for the stack, and it is also a good test to write.

Daily temperatures: distances instead of values

A common variation asks for the number of days until a warmer day, not the warmer value itself. You store the distance i - top instead of a[i]. The distance is the number of steps from the waiting day to the warmer day.

Given the daily temperatures 73 74 75 71 69 72 76 73, the answers are 1 1 4 2 1 1 0 0. Day 0 is 73, and day 1 is 74, so one day later is warmer. Day 2 is 75, and the next warmer day is day 6, which is 76, so the wait is 4 days. The last two days have no warmer day after them, so their answer is 0.

The program reads the number of days, then the temperatures. Type 8 on the first line of the Input box and the eight temperatures on the second line.

Input box:

8
73 74 75 71 69 72 76 73

Output:

1 1 4 2 1 1 0 0

The default value is 0, not -1, because a day with no warmer day has a wait of zero in this problem. The problem statement decides the default, and the code must follow it. Always read the statement for the value to use when there is no answer, because -1 and 0 both appear in real questions.

Stock span: counting backwards

The stock span problem asks something different. For each day, count how many days in a row, going backwards and including today, had a price at most today's price. Today always counts, so the span is at least 1.

Take the prices 100 80 60 70 60 75 85. Day 0 has span 1, because nothing comes before it. Day 3, with price 70, looks back: the 60 on day 2 is at most 70, so count it. The 80 on day 1 is more than 70, so stop. The span is 2, counting today and day 2. Day 6, with price 85, looks back and finds 75, 60, 70, 60 and 80, all at most 85. Then it finds 100, which is bigger, and stops. The span is 6.

The monotonic stack handles this with a small change to the rule. Pop while the top price is at most today's price, not strictly less. Then the answer is the distance to the top that remains, which is the nearest earlier day with a bigger price. If the stack is empty, every earlier day was at most today's price, so the span is i + 1.

Input box:

7
100 80 60 70 60 75 85

Output:

1 1 1 2 1 4 6

Here the stack holds indexes whose prices are strictly decreasing from bottom to top. The <= in the pop condition is deliberate. A day with an equal price counts toward the span, so an equal earlier day must be popped, not left as the stopping point. Change <= to < and the span for repeated prices becomes wrong. Run the program on the input 5 then 5 5 5 5 5 to see that the spans count up one by one, which is the correct behaviour for equal prices.

The next smaller element

Flip the comparison and you get the next smaller element. The stack now holds indexes whose values increase from bottom to top, and it pops while the top is bigger than the new value. This is the same structure with the inequality reversed. You can check that you understand it by predicting the output before you run this program.

Input box:

6
4 8 5 2 25 1

Output:

2 5 2 1 1 -1

Check the first answer by hand. The 4 is followed by 8, 5 and then 2. The first value smaller than 4 is 2, so the answer is 2. The 8 is followed immediately by 5, so its answer is 5. The 25 is followed by 1, which is the first smaller value, so its answer is 1. The 1 has nothing smaller after it, so the answer is -1.

Circular arrays: walk the array twice

Sometimes the array wraps around. After the last element, the search continues from the first. A ring of shops, or the days of a repeating week, are examples. The trick is to walk the array twice, using i % n to find the real position. The first lap pushes new indexes onto the stack. The second lap only pops, because every index has already been pushed.

For the array {1, 2, 1, 3, 2} the circular next greater answers are 2 3 3 -1 3. The 3 at position 3 has no bigger value anywhere in the ring, so it gets -1. The 2 at position 4 wraps around to position 0, where it finds 1, then 2, then 1, then 3, so its answer is 3.

Input box:

5
1 2 1 3 2

Output:

2 3 3 -1 3

The second lap is what makes this work. Without it, the 2 at the end would never see the values at the start. Notice also that the code pushes only on the first lap. If it pushed on both laps, an index could sit on the stack twice, and the answers would be written in the wrong place.

Debugging walkthrough: the duplicate-value bug

The most common bug in this family is the choice between < and <=. The problem asks for a strictly greater value. Using <= in the pop condition silently answers a different question: "the next value that is greater or equal". Here is the bug in action. Predict the output before you run it.

Output:

3 5 -1

The correct answer is 5 5 -1, because no 3 is strictly bigger than the 3 before it, but the 5 is bigger than both. The buggy program gave the first 3 an answer of 3, which is not greater than itself. Trace it: at i = 1, the top is index 0 with value 3, and 3 <= 3 is true, so the code wrote 3 as the answer for index 0 and popped it. The fix is to change <= back to <. When you test a stack algorithm, always include a case with equal values, because equal values are where strict and loose comparisons differ.

The invariant: why the stack is always ordered

An invariant is a statement about an algorithm that stays true after every step. Knowing the invariant is how you prove that an algorithm is correct, and it is also how you spot the step that breaks it. The monotonic stack has two invariants, and both are worth stating in your own words.

The first invariant is about order. Read the stack from bottom to top, and look at the values at those indexes. The values never increase. Each one is equal to or smaller than the one below it. Why is that always true? When a new index arrives, the loop has just popped every index whose value was smaller than the new value. So the value now on top is at least as large as the new value. The new index is pushed above it, and the order holds.

The second invariant is about answers. Every index still on the stack has no answer yet. No value to its right has been bigger than it, because if one had arrived, the loop would have popped it. So the stack is exactly the list of indexes that are still waiting.

These two facts prove the algorithm. When the loop pops an index because of a new value a[i], that index's answer must be a[i]. Why? Any value between the popped index and i was pushed after it, and each of those values was too small to pop it, or it would have been popped earlier. So no value between them was bigger, and a[i] is the first bigger one. The proof is short, and it depends only on the invariant.

Now you can see why the comparison matters. If the loop popped on <= instead of <, the first invariant would become strict, and the second would be broken for equal values. That is the duplicate-value bug from the debugging walkthrough. A good habit is to state the invariant before you code a stack algorithm, then check that every line of the loop keeps it.

Stock span, traced step by step

The stock span loop is the same algorithm with a different pop rule, so a full trace is useful. Take the prices 100 80 60 70 60 75 85. The table shows the stack of indexes after each day, and the span written for that day. Remember that the span counts today, and the distance to the top that remains gives the span.

The spans are 1 1 1 2 1 4 6, which is the answer the program prints. Look at day 5 closely. The stack held the days 1, 3 and 4 before the day with price 75 arrived. Days 4 and 3 are at most 75, so they are popped. Day 1 has price 80, which is bigger, so the loop stops there. The span is 5 - 1 = 4. It counts day 5 itself and the three days 2, 3 and 4. Day 2 is not on the stack any more, because day 3 with price 70 already covered it. That is safe, because a price that is at most day 3's price, and day 3 is at most day 5's price, is also at most day 5's price.

That last point is the reason the stack can forget days. Once a day is popped by a later day with a bigger or equal price, every day it could have spanned is also covered by that later day. This is the same argument as the invariant, applied to spans instead of answers.

Checking your answer with a brute force

When you are unsure whether a fast algorithm is correct, write a slow version whose correctness is obvious. For next greater, a slow version scans to the right for each position. It is O(n squared), so it is too slow for real input, but it is easy to read and hard to get wrong. Then compare the two on many small random arrays. If they always agree, the fast version is very likely correct. If they disagree, print the array that failed, and trace both versions on it.

This technique is one of the best habits in algorithm work. The slow version is your reference. You do not need to trust it for speed, only for correctness. A typical test loop generates an array of 1 to 10 numbers with values from -5 to 5, runs both versions, and stops at the first difference. Small values matter, because they create many duplicates, and duplicates are where strict and loose comparisons differ. Random tests with large values would almost never hit those cases.

Keep the brute force in your notes, and use it whenever you change a comparison or add a special case. It costs a few minutes and catches most of the mistakes that this lesson describes.

Common mistakes

Mistake 1: storing values instead of indexes. If the stack holds values, you cannot tell where to write the answer, and you cannot compute distances. Store indexes, and look up the value with a[st.top()] when you need it.

Mistake 2: the wrong default answer. The problem decides whether a missing answer is -1, 0 or something else. The daily temperatures problem uses 0. The next greater problem uses -1. Copying the wrong default is a silent error, because the code still runs.

Mistake 3: the wrong comparison for equal values. Use < for strictly greater, and <= only when the problem counts equal values, as in the stock span. The debugging example above shows the cost of mixing them up.

Mistake 4: forgetting to include <vector>. If you use vector without the include, g++ prints this:

e6.cpp:3:5: error: 'vector' was not declared in this scope
    3 |     vector<int> v = {1, 2};
      |     ^~~~~~

The fix is #include <vector>. The same rule applies to every standard container, so get into the habit of listing the headers you need.

Mistake 5: reading the stack as a list of values. The stack holds indexes. When you write st.top(), you get the index. The value is a[st.top()]. Mixing the two produces answers that look plausible but are wrong.

Mistake 6: thinking the nested loop is O(n squared). The inner while pops at most n items over the whole run. Count the total pushes and pops, not the loop shape, to find the cost.

Mistake 7: forgetting that a circular walk must not push twice. The second lap in the circular version only pops. Pushing again would put each index on the stack twice.

Variations and edge cases

Each variation changes one thing from the basic algorithm. Keep a table like this one in your notes:

The previous greater row is worth a moment. The popped entries are exactly the ones that cannot be the previous greater for any later index, so the top that remains after popping is the answer. The stock span is the same idea, expressed as a distance.

Edge cases to test: an array with one element (every answer is the default), a strictly increasing array (each element is popped by the next one), a strictly decreasing array (nothing is popped until the end), and an array full of equal values (the strict and loose versions disagree).

Interview questions and what they test

These questions use the monotonic stack in different ways:

• Largest rectangle in a histogram. For each bar, find the nearest shorter bar on the left and on the right. The width is the distance between them, and the area is the height times the width. Practice exercise 9 asks you to build it.
• Trapping rain water. Water sits between taller bars. A monotonic stack finds the walls on each side of every dip.
• Remove duplicate letters so the result is the smallest. The stack keeps letters in increasing order and pops a letter when a smaller one arrives and the letter occurs again later.
• Next warmer day. This is the daily temperatures problem, and it is the most common warm-up question.

When an interviewer asks about these, start by saying which direction you scan, which comparison pops, and what you store. Then state the O(n) argument by counting pushes and pops. That order shows you understand the structure, not just the code.

Real-world uses

Any task that asks for "the nearest earlier item that is bigger" or "the nearest earlier item that is smaller" has this shape. Price-tracking tools that count how many days a price has stayed low use the span idea. Tools that measure how wide a region of tall values can be use the histogram idea from the practice exercises. In each case a monotonic stack is the efficient answer, and the O(n) cost means it still works on long records.

Practice

1. Easy. Find the next smaller element for each position of {5, 3, 8, 1} by hand, then check your answer with the program above. Expected answer: 3 1 1 -1.

2. Easy. For the array {2, 2, 2}, find the next greater element for each position. Explain why the answer is not 2 2 -1.

3. Easy. Compute the stock span for the prices 5 5 5 5 5. Explain why each span is one larger than the one before.

4. Medium. Change the daily temperatures program so that it prints -1 for days with no warmer day, instead of 0. Explain which line changes and why.

5. Medium. Write a function that returns, for each position, the index of the previous greater element, or -1 if there is none. Hint: after popping, the top that remains is the answer.

6. Medium. Given the prices of a stock, find the largest profit from buying on one day and selling on a later day, using the next greater idea. Hint: for each day, the best sale is the highest price later, and the next greater element finds a relevant price.

7. Medium. Explain, without code, why the stock span program can use the same stack as the next greater program but with <= in the pop condition.

8. Medium. Given {1, 4, 2, 3}, list the stack contents after each step of the next greater algorithm, as indexes.

9. Hard. Largest rectangle in a histogram. Given bar heights, find the largest rectangle that fits between bars. Hint: for each bar, the rectangle using that bar's height extends until the nearest shorter bar on each side. A stack of increasing heights finds both sides, and you measure a rectangle when a bar is popped.

10. Hard. Trapping rain water. Given bar heights, compute how much water is trapped above the bars after rain. Hint: water above a dip is limited by the shorter of the tallest bars on its left and right. A stack can find the walls for each dip when a bar is taller than the top.

What you now know

• The next greater element for each position can be found in O(n) with a monotonic stack of indexes.
• A monotonic stack stays sorted, so every pop is the moment an answer is found.
• Each index is pushed once and popped at most once, so the nested-looking loop is O(n) in total.
• Store indexes, not values, so you know where to write the answer and can compute distances.
• Read the statement for the default answer and for whether equal values count. The comparison must match.
• Circular arrays are handled by walking twice with i % n and pushing only on the first lap.