Daily temperatures and stock span

Why this matters

Two questions come up often in interviews and in real data work. How many days must I wait until the weather gets warmer? For how many days in a row has a stock stayed at or below today's price? The two questions look different, but both ask the same thing in disguise: find the nearest item next to today's item that breaks a rule. One stack pattern answers both in a single pass over the data.

This lesson starts with a small list of numbers and a loop anyone would write first. Then it builds the stack pattern one step at a time, applies it to both questions, and compares the answers with the loop. You will also see how one changed rule turns the same pattern into the other answer, and how to test your code against the slow version so you can trust the fast one.

Two questions with the same shape

Start with daily temperatures. Suppose you record the high temperature for eight days in a row:

day:          0   1   2   3   4   5   6   7
temperature:  73  74  75  71  69  72  76  73

For each day, the question is: how many days do I wait until a warmer day? Day 0 is 73. Day 1 is 74, which is warmer, so the wait is 1 day. Day 2 is 75. Its next warmer day is day 6, which is 76, so the wait is 4 days. Day 6 is 76, and nothing after it is warmer, so the answer is 0. A day with no warmer day after it gets 0.

Now stock span. A stock's price is recorded once per day. The span of a day is the number of days in a row, counting today and going backwards, where the price was at or below today's price. Take these prices:

day:    0    1   2   3   4   5   6
price:  100  80  60  70  60  75  85

For day 5, the price is 75. Going backwards, day 4 is 60, which is at or below 75, so it counts. Day 3 is 70, which counts. Day 2 is 60, which counts. Day 1 is 80, which is above 75, so the run stops. The count is 4 days (days 2 to 5), so the span for day 5 is 4.

Both questions look left or right from one item and stop at the first item that breaks a rule. That shape is what the stack pattern solves.

The slow way first

The simplest program for daily temperatures has two nested loops. The outer loop picks a day. The inner loop looks forward for the first warmer day.

std::vector<int> daily_temperatures_brute(const std::vector<int>& temp, long long& ops) {
    std::vector<int> answer(temp.size(), 0);
    for (std::size_t i = 0; i < temp.size(); ++i) {
        for (std::size_t j = i + 1; j < temp.size(); ++j) {
            ++ops;  // count each comparison
            if (temp[j] > temp[i]) {
                answer[i] = static_cast<int>(j - i);
                break;  // stop at the first warmer day
            }
        }
    }
    return answer;
}

The variable ops counts how many comparisons the loop makes. It is only there so you can see the cost. The break stops the inner loop as soon as a warmer day is found, so the loop is fast when warm days come soon. It is slow when they do not.

The stock span loop is similar, but it looks backwards. It counts days going back from today while the price is at or below today's price.

std::vector<int> stock_span_brute(const std::vector<int>& price, long long& ops) {
    std::vector<int> span(price.size(), 0);
    for (std::size_t i = 0; i < price.size(); ++i) {
        int count = 0;
        for (std::size_t j = i + 1; j-- > 0;) {  // j goes i, i-1, ..., 0
            ++ops;
            if (price[j] > price[i]) break;  // a higher price ends the run
            ++count;
        }
        span[i] = count;
    }
    return span;
}

The expression j-- > 0 compares j with 0 and then lowers j by one. It is a common way to count down through an unsigned index without the index ever becoming negative. The first check lowers j from i + 1 to i, so today is always counted.

The worst case for the daily temperatures loop is a list where every day is colder than the one before it. Then no day has a warmer day after it, and the inner loop always runs to the end. The code below measures that case for three list sizes.

for (int n : {1000, 2000, 4000}) {
    std::vector<int> falling(n);
    for (int i = 0; i < n; ++i) falling[i] = n - i;
    long long brute_ops = 0;
    daily_temperatures_brute(falling, brute_ops);
    std::cout << "n=" << n << " brute comparisons=" << brute_ops << '\n';
}

Real output from g++ 15.2 with -std=c++20 -Wall -Wextra -O2:

n=1000 brute comparisons=499500
n=2000 brute comparisons=1999000
n=4000 brute comparisons=7998000

Each time the list doubles, the number of comparisons roughly quadruples. The count is n times (n minus 1) divided by 2. That growth is written as O(n squared), meaning the work grows with the square of the input size. A list of 100,000 days would need about five billion comparisons in this worst case. The stack method below does the same job with about n pushes and at most n pops.

The template: a stack of days that are still waiting

A stack is a pile. You can only add to the top (this is called push) and only remove from the top (this is called pop). The last item you put on is the first one you take off.

The stack in this pattern holds the positions of days that are still waiting for an answer. Think of each waiting day as a sticky note on a pile. When a new day arrives, it checks the note on top of the pile. If the new day answers the note on top, that note is removed and its answer is written. The check repeats until the top note is not answered by the new day. Then the new day gets its own note on top.

The template has three steps. For each new position i from left to right:

1. While the stack is not empty and the top position is waiting for something that i provides, pop it and record the answer for it.
2. Push i. It now waits for a later day.
3. When the walk ends, any position still on the stack gets no answer, so its value stays at the default.

Two details matter. First, the stack stores positions, not values. A position tells you where to write the answer. A value would tell you what the number is but not where it belongs in the answer list. Second, the stack is always sorted by value. Because a waiting value is removed as soon as something bigger comes along, the values left on the stack form a sorted list from bottom to top. That order is what makes the top the only item you ever need to check.

The rest of the lesson fills in the two rules: what makes a waiting item leave the stack, and what gets written when it leaves.

Daily temperatures, step by step

Here is the full function for daily temperatures. A waiting day leaves the stack when a warmer day arrives. Its answer is the distance from the waiting day to the warmer day.

std::vector<int> daily_temperatures(const std::vector<int>& temp) {
    std::vector<int> answer(temp.size(), 0);
    std::stack<std::size_t> waiting;  // days that have not yet found a warmer day
    for (std::size_t day = 0; day < temp.size(); ++day) {
        while (!waiting.empty() && temp[waiting.top()] < temp[day]) {
            std::size_t cold = waiting.top();
            waiting.pop();
            answer[cold] = static_cast<int>(day - cold);
        }
        waiting.push(day);
    }
    return answer;
}

The while loop is the first step of the template. The if check is missing on purpose: a while keeps popping as long as the new day is warmer than the top. This matters when one warm day answers several cold days at once.

Trace the list from the first example. The table shows the stack before each day is handled, and the answers written during that step. Stack contents are listed bottom first, and each entry shows its day number and temperature.

Read the step for day 5 closely. Days 4 and 3 are both waiting, and day 5 (72) is warmer than both. The top is day 4, which gets its answer first, and then day 3, which gets its answer next. That is why the while loop is needed.

Running this function on the eight days gives:

1 1 4 2 1 1 0 0

Every position appears on the stack once and leaves it at most once. Each push and each pop costs a fixed amount of work. So the total work grows in a straight line with the number of days, which is O(n). The brute-force loop does far more work on the same list.

Stock span, step by step

The stock span question is the same shape with the rule turned around. Instead of finding the next higher day, find the nearest earlier day with a higher price. Once you know that earlier day, the span is simply today's position minus its position.

The stack holds earlier days whose price is still higher than every price since then. When a new price arrives, every earlier day whose price is at or below the new price is no longer useful. A later day will never look past today to find a higher price, because today is at or above those prices. So those days are removed. What is left on top is the nearest earlier day with a higher price, and that is where the span stops.

std::vector<int> stock_span(const std::vector<int>& price) {
    std::vector<int> span(price.size(), 0);
    std::stack<std::size_t> higher;  // earlier days whose price is still above what comes after
    for (std::size_t day = 0; day < price.size(); ++day) {
        while (!higher.empty() && price[higher.top()] <= price[day]) {
            higher.pop();
        }
        span[day] = static_cast<int>(higher.empty() ? day + 1 : day - higher.top());
        higher.push(day);
    }
    return span;
}

There are two differences from the daily temperatures code. The pop condition uses <= instead of <, because a price equal to today's still counts toward the span. And the answer is written to today, not to the popped day. Today's answer is computed after the pops, from the top that is left.

The empty case needs care. If the stack is empty after the pops, no earlier day had a higher price. Then the run reaches back to day 0, so the span is day + 1. For day 0 that is 1, which is correct: the first day has only itself to count.

Trace the seven prices from the example:

Running the function gives:

1 1 1 2 1 4 6

Check day 6 by hand. Going back from 85, every earlier price is at or below 85 until day 0, which is 100. So the run covers days 1 to 6, which is 6 days. The answer is 6, matching the output.

The brute-force span loop from earlier gives the same numbers. Both print 1 1 1 2 1 4 6 on this input.

The same template, one rule changed

The two problems share the same walk, the same stack and the same push step. Only two things change: when a waiting item leaves, and where the answer is written.

The word "strictly" in the first row is important. A day that is exactly as warm as the waiting day does not count as warmer, so the waiting day keeps waiting. In the stock span, equal prices do count, so the rule uses <=. Getting the strictness wrong is the most common bug in this pattern, and the mistakes section below shows what it does to the output.

A harder example: the week wraps around

Suppose the list is a repeating week. Day 6 is followed by day 0 again. Now a day near the end can find a warmer day at the start of the list. A plain pass over the list would miss those answers.

The trick is to walk the list twice. Let step run from 0 to twice the length minus 1, and take the real day as step modulo the length. Only the first pass pushes days onto the stack. The second pass gives the waiting days their last chance to find a warmer day. The distance is step - cold, which is the distance in the unrolled list of two passes.

std::vector<int> daily_temperatures_circular(const std::vector<int>& temp) {
    std::size_t n = temp.size();
    std::vector<int> answer(n, 0);
    std::stack<std::size_t> waiting;
    for (std::size_t step = 0; step < 2 * n; ++step) {
        std::size_t day = step % n;  // wrap back to the start of the list
        while (!waiting.empty() && temp[waiting.top()] < temp[day]) {
            std::size_t cold = waiting.top();
            waiting.pop();
            answer[cold] = static_cast<int>(step - cold);
        }
        if (step < n) waiting.push(day);  // only the first pass adds days
    }
    return answer;
}

Take the list 50 60 40 45 70. Day 4 (70) is the warmest day, so no later day is warmer, even when the week wraps. Its answer is 0. Day 0 (50) gets 1 from day 1 (60). Day 1 (60) waits until day 4 (70), which is 3 days later. Day 2 (40) gets 1 from day 3 (45), and day 3 gets 1 from day 4.

Running it on this list and on the eight-day list from before:

1 1 4 2 1 1 0 2 | brute: 1 1 4 2 1 1 0 2
1 3 1 1 0 | brute: 1 3 1 1 0
random mismatches: 0

The last day of the first list, 73, gets 2 because the wrap-around leads to day 1 (74), which is 2 steps away. The brute version in the same program checks each day against the next n days modulo the length. The random test built 3000 lists with 1 to 20 values from 0 to 9, and the two versions agreed on every list.

Common mistakes

Storing values instead of positions. A beginner often pushes the temperature, not the day number. The program then runs, but it cannot write the answer, because it has no idea which day the value came from. The fix is to store the position and read the value from the array when you need it, as the code above does with temp[waiting.top()].

Using the wrong comparison. Using <= in daily temperatures turns "warmer" into "warmer or equal". The next example shows the output. The list is 70, 70, 71. The correct answer for day 0 is 2, because day 2 (71) is the first warmer day. The wrong version pops day 0 as soon as day 1 arrives, because 70 is equal to 70.

correct:  2 1 0
with <=:  1 1 0

Using < in stock span. The same mistake in the other direction stops the span too early. The span for a list of three equal prices should count all the equal days. Real output from the version with < in the pop loop:

with <:  1 1 1
correct: 1 2 3

Comparing an int index with a size_t size. The loop for (int i = 0; i < t.size(); ++i) looks harmless, but t.size() returns an unsigned type. GCC reports this with -Wall:

bad1.cpp:6:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    6 |     for (int i = 0; i < t.size(); ++i) {
      |                     ~~^~~~~~~~~~

Use std::size_t for every position, as the code in this lesson does. Then the comparison is between two unsigned values, and the warning goes away.

Calling top() or pop() on an empty stack. The stock span code is safe because it checks !higher.empty() first. A common version of the trapping rain water method (the next lesson) forgets that check. The C++ standard calls this undefined behaviour, which means the program may do anything. Without help, it often appears to work. To make the mistake visible, compile with -D_GLIBCXX_ASSERTIONS, which makes the GNU standard library check the call. This program has no empty check:

#include <stack>
#include <vector>
#include <cstddef>
int main() {
    std::stack<std::size_t> walls;
    walls.push(0);
    std::size_t bottom = walls.top();
    walls.pop();
    walls.pop();  // the stack is empty here
    return static_cast<int>(bottom);
}

Real output from g++ -std=c++20 -Wall -D_GLIBCXX_ASSERTIONS -O0, followed by the exit code. The path and line number depend on the compiler version:

/usr/include/c++/15/bits/stl_stack.h:333: void std::stack<_Tp, _Sequence>::pop() [with _Tp = long unsigned int; _Sequence = std::deque<long unsigned int, std::allocator<long unsigned int> >]: Assertion '!this->empty()' failed.
exit=134

The fix is to check empty() before every top() and every pop().

Off-by-one distances. The answer is the number of days to wait, which is the difference of positions. Adding 1 to it, or using day - cold - 1, gives a wrong count. Test on a tiny list, such as 70 71, where the answer must be 1. A quick check like this catches the mistake before any bigger test does.

Practice

Exercise 1. Trace daily_temperatures by hand on 70 72 71 75. Write the stack after each day and the final answer list.

Show the answer

Day 0 (70) waits. Day 1 (72) is warmer, so day 0 gets 1 and day 1 waits. Day 2 (71) waits on top of day 1. Day 3 (75) is warmer than 71 and than 72, so day 2 gets 3 - 2 = 1 and day 1 gets 3 - 1 = 2. Day 3 has no warmer day, so it gets 0. The answer list is 1 2 1 0, which matches the real output.

Exercise 2. Compute the stock span for the prices 10 12 9 9 15 by hand. Then check your answer with stock_span.

Show the answer

Day 0: no earlier day, span 1. Day 1 (12): day 0 (10) is at or below 12, and nothing before it, so span 2. Day 2 (9): day 1 (12) is above 9, so span 1. Day 3 (9): day 2 (9) is at or below 9, then day 1 (12) is above, so span 2. Day 4 (15): every earlier price is at or below 15, so the span is 5. The answer is 1 2 1 2 5, which matches the real output.

Exercise 3. Change daily_temperatures so it returns the index of the next warmer day instead of the distance. Use -1 when there is no warmer day.

Show the answer

Start the answer list with -1 instead of 0. In the while loop, write answer[waiting.top()] = static_cast<int>(day); before the pop, and leave the rest of the loop the same. On 73 74 75 71 69 72 76 73 the answers are 1 2 6 5 5 6 -1 -1. Day 2 (75) points to index 6 (76). To get the distance back, subtract the day number from the index.

Exercise 4. Explain why the same list 70 70 71 gives a different answer when the pop test is <=. Name the day whose answer changes.

Show the answer

With <=, day 1 (70) pops day 0 (70) because 70 is at most 70. Day 0 is given the answer 1, which is the distance to day 1, a day with the same temperature, not a warmer one. The correct answer is 2, the distance to day 2 (71). Only day 0's answer changes, from 2 to 1.

Exercise 5. Use the stock_span_brute loop from earlier to count how many comparisons it makes on the list 5 5 5 5. Explain whether the count grows faster or slower than the stack method as the list gets longer.

Show the answer

For i from 0 to 3, the loop checks price[j] > price[i] going back from i. Day 0 makes 1 comparison, day 1 makes 2, day 2 makes 3, and day 3 makes 4. The total is 10 comparisons. Since no price is higher, every day scans back to day 0, so the total is n times (n plus 1) divided by 2. That grows with the square of the list length, while the stack version does about one push and one pop per day, which grows in a straight line.

Summary

• Both questions ask for the nearest earlier or later item that breaks a rule, so one stack pattern solves both.
• The stack holds positions, and the top is the only one checked for each new item.
• In daily temperatures, the popped day gets the answer, and the pop test is strictly warmer.
• In stock span, the answer goes to today, computed from the top left after popping, and equal prices count.
• The brute-force loops are simple and correct, but their work grows with the square of the list length. Use them to check the fast version on random inputs.