Daily temperatures and stock span in Python

Why this matters

A large share of array questions ask about the neighbours of each item. For each day, how long until the weather gets warmer? For each price, how many earlier days had a price no higher than today's? A direct answer for each item needs a scan through the other items, and the scans add up. With n items, the total work is about n times n, which is written O(n squared). A monotonic stack, which is a stack that stays in one order, answers the same questions in one pass, so the work grows with n instead of with n squared.

This lesson uses two problems that share one loop. The loop is used twice, once to look ahead and once to look back, so you can see what changes and what stays the same. The next lesson in this module, on trapping rain water, uses the same stack in a different way.

Words you will need

• Index: the position of an item in a list, counted from 0. The first item has index 0.
• Stack: a pile where you add and remove items only at the top. The last item added is the first one removed. In Python, a plain list does this job. append adds to the top, pop removes the top and returns it, and stack[-1] reads the top without removing it.
• Monotonic stack: a stack whose values always go in one direction from bottom to top, either only up or only down.
• Brute force: the simplest correct method, which tries every possibility. It is slow, but it is easy to trust, so it is a good reference for checking a faster method.
• Span: a count of days in a row, ending today, that meet a rule.
• Amortised cost: the average cost per step over a whole run. One step can be expensive, but the average stays small.

Two questions about a list

The first question is called daily temperatures. You are given the temperature for each day. For each day, count how many days you must wait until a warmer day. If no warmer day ever comes, the answer is 0.

Take the temperatures [73, 74, 75, 71, 69, 72, 76, 73]. Day 0 is 73. Day 1 is 74, which is warmer, so the answer for day 0 is 1 day. Day 2 is 75, and day 3 is 71, so day 2 waits for day 6, which is 76. The wait is 6 minus 2, which is 4 days. Day 6 is 76, and no later day is warmer, so its answer is 0.

The second question is called stock span. You are given a price for each day. For each day, count how many days in a row, going backwards and including today, had a price no higher than today's price. The span counts the streak, so it looks at the past instead of the future.

Take the prices [100, 80, 60, 70, 60, 75, 85]. Day 0 has no earlier days, so its span is 1. Day 3 has price 70. The day before, 60, is no higher than 70, so it counts. The day before that, 80, is higher than 70, so the streak stops there. The span for day 3 is 2.

The brute force for daily temperatures

For each day, look forward one day at a time until you find a warmer day. Record the distance. If you reach the end, the answer stays 0.

def warmer_brute_force(temps):
    n = len(temps)
    answer = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temps[j] > temps[i]:
                answer[i] = j - i
                break
    return answer

The break stops the inner loop as soon as a warmer day is found. That helps on easy inputs, but it does not help in the worst case. If the temperatures fall every day, no day is ever followed by a warmer day, so each inner loop runs to the end. For 5 days with temperatures 9, 8, 7, 6, 5, the scans check 4, 3, 2 and 1 days, a total of 10 checks. For n days the total is close to n times n divided by 2, which is O(n squared). Doubling the number of days makes the work about four times larger.

Here is the output of the program for the example above. The output in this lesson was produced by running Python 3.14 on the code in the lesson. The mistake sections use small changed copies of that code.

temps   [73, 74, 75, 71, 69, 72, 76, 73]
brute   [1, 1, 4, 2, 1, 1, 0, 0]
stack   [1, 1, 4, 2, 1, 1, 0, 0]

The shared template

Both problems use the same loop. Scan the list once from left to right. Keep a stack of positions that are still waiting for something. For each new position, pop every waiting position that the new value settles. Then push the new position, because it may be settled later.

for each position i, from left to right:
    while the stack is not empty and the top position is settled by item i:
        pop the top position and do the work it needs
    push i onto the stack

The stack holds positions, not values. A position is what lets you compute a distance, because the distance is today's index minus the earlier index. Storing only the value would lose that information.

The pop condition and what you do with a popped position are the parts that change between the two problems. In daily temperatures, the new day settles a waiting day when the new day is warmer, and the popped day gets its answer. In stock span, popped days get no answer, and the new day reads the top of the stack after the pops.

Daily temperatures with the stack

The stack holds the days that have not yet found a warmer day. Each new day checks the top of the stack. If the new day is warmer than the top day, the top day has found its answer. The distance is the new day's index minus the top day's index. Pop it, and check the next day down. Repeat until the top is not cooler than the new day, or the stack is empty. Then push the new day.

def warmer_with_stack(temps):
    answer = [0] * len(temps)
    waiting = []
    for day, temp in enumerate(temps):
        while waiting and temp > temps[waiting[-1]]:
            earlier = waiting.pop()
            answer[earlier] = day - earlier
        waiting.append(day)
    return answer

enumerate(temps) gives each pair of index and value, so the loop has both at once. The condition waiting and temp > temps[waiting[-1]] first checks that the list is not empty. Python reads the conditions from left to right and stops at the first one that is false, so temps[waiting[-1]] is never read from an empty list.

The program also prints a trace, which shows the stack before and after each day. In the trace, the stack is written with the top first, so the first number is the top position.

day 0 temp 73 | stack before [] | popped none | stack after [0]
day 1 temp 74 | stack before [0] | popped 0 | stack after [1]
day 2 temp 75 | stack before [1] | popped 1 | stack after [2]
day 3 temp 71 | stack before [2] | popped none | stack after [3, 2]
day 4 temp 69 | stack before [3, 2] | popped none | stack after [4, 3, 2]
day 5 temp 72 | stack before [4, 3, 2] | popped 4 3 | stack after [5, 2]
day 6 temp 76 | stack before [5, 2] | popped 5 2 | stack after [6]
day 7 temp 73 | stack before [6] | popped none | stack after [7, 6]

Read day 5 carefully. The stack before day 5 is [4, 3, 2], so the top is day 4, which is 69. Day 5 is 72, which is warmer, so day 4 is popped with answer 5 minus 4, which is 1. Next is day 3, which is 71. Day 5 is also warmer, so day 3 is popped with answer 5 minus 3, which is 2. The next position is day 2, which is 75. Day 5 is not warmer than 75, so the loop stops. Day 5 is pushed on top. The stack is now [5, 2], which matches the trace.

Before day 5, the stack held days 2, 3 and 4, with temperatures 75, 71 and 69. From bottom to top the temperatures go down. That is the monotonic part. A day is pushed only after every cooler day above it has been popped, so each day on the stack is no warmer than the days below it.

Days still in the stack at the end, such as day 6 and day 7 in the example, keep their answer of 0. That is because no warmer day ever came for them, and the list starts at 0.

Stock span with the same loop

For stock span, the question is about the past, so there is no waiting. The stack holds days that could still be the nearest higher day for a future day. When a new day arrives, pop every day whose price is no higher than the new price. Those days can never be the nearest higher day for any later day, because the new day is closer and at least as high. After the pops, the top of the stack is the nearest earlier day with a higher price. The span is today's index minus that index. If the stack is empty, no earlier day was higher, so the streak reaches back to day 0. The span is then the day index plus 1.

def span_with_stack(prices):
    span = [0] * len(prices)
    higher = []
    for day, price in enumerate(prices):
        while higher and prices[higher[-1]] <= price:
            higher.pop()
        span[day] = day + 1 if not higher else day - higher[-1]
        higher.append(day)
    return span

The loop shape is the same as before. The pop condition is now "the top price is no higher", written with <=. Nothing is recorded for the popped days, because their answers were already decided. The answer for today is read after the pops, from whatever sits on top. The line day + 1 if not higher else day - higher[-1] is a conditional expression. It reads as "day plus 1 if the stack is empty, otherwise day minus the top index".

The trace for the example [100, 80, 60, 70, 60, 75, 85] shows the work.

day 0 price 100 | stack before [] | popped none | span 1 | stack after [0]
day 1 price 80 | stack before [0] | popped none | span 1 | stack after [1, 0]
day 2 price 60 | stack before [1, 0] | popped none | span 1 | stack after [2, 1, 0]
day 3 price 70 | stack before [2, 1, 0] | popped 2 | span 2 | stack after [3, 1, 0]
day 4 price 60 | stack before [3, 1, 0] | popped none | span 1 | stack after [4, 3, 1, 0]
day 5 price 75 | stack before [4, 3, 1, 0] | popped 4 3 | span 4 | stack after [5, 1, 0]
day 6 price 85 | stack before [5, 1, 0] | popped 5 1 | span 6 | stack after [6, 0]

Look at day 6. The price is 85. The stack before it is [5, 1, 0]. Day 5 at 75 is no higher than 85, so it is popped. Day 1 at 80 is no higher than 85, so it is popped. Day 0 at 100 is higher, so the loop stops there. The span is 6 minus 0, which is 6. Check it by hand: the prices on days 1 through 6 are all no higher than 85, and day 0 is 100, so the streak runs from day 1 to day 6, which is six days.

The stock span stack also stays monotonic. From bottom to top, the prices go down, because a new day is pushed only after every price on the stack that is no higher than its own has been popped, so the price just below it is strictly higher.

Comparing the two problems

Both problems use the same loop, and their differences are small but important.

The first problem looks forward, so answers are written later, when a warmer day arrives. The second problem looks backward, so each answer can be written right away. This is why stock span can run on a live feed of prices, one day at a time, with no need to see the future. Daily temperatures needs the future by its nature, because the answer for a day depends on days that have not arrived yet.

Brute force versus the stack

The brute force for stock span looks back from each day until it finds a higher price. Take 1000 prices that rise every day, so the price on day i is i (day 0 is 0, day 1 is 1, and so on). Every earlier price is no higher than today's, so each day's backward scan runs to day 0. Day 999 scans 999 earlier days. The total work is 999 plus 998 and so on down to 0, which is 499,500 inner-loop steps. The full program below counts these steps and prints the count.

rising n=1000 brute inner steps 499500
rising n=1000 span first 5 [1, 2, 3, 4, 5]
rising n=1000 stack span first 5 [1, 2, 3, 4, 5]

The stack version does far fewer steps on the same input. Each day is pushed onto the stack exactly once. Each position is popped at most once, because a popped position never returns. So the total number of pushes and pops is at most twice n, which is about 2000 for n equal to 1000. The average cost per day is therefore a small constant. This averaging over many steps is what amortised means: a single day can pop many positions, but over the whole run the number of pops cannot exceed the number of pushes.

The stack solution is O(n) in time and O(n) in space, where space means the extra memory the method uses. The brute force is O(n squared) in time and O(1) in extra space, because it needs only a few variables.

Worked example with equal values

A harder case uses equal prices. The rule says a previous day counts when its price is no higher than today's. "No higher" includes equal, so an equal price counts toward the span. Look at the prices [5, 5, 5, 3, 5].

prices      [5, 5, 5, 3, 5]
brute       [1, 2, 3, 1, 5]
stack       [1, 2, 3, 1, 5]

For day 4, the price is 5. Going backwards, day 3 at 3 is no higher, so it counts. Day 2 at 5 is equal, so it counts. Day 1 at 5 counts, and day 0 at 5 counts. The streak is five days long, so the span is 5. The pop condition <= removes equal values from the stack, and that is correct for this problem, because today's day is closer and just as high, so an equal earlier day can never be the nearest higher day for a later one.

The comparison operator matters. If the condition is <, equal values stay on the stack, and the answer is wrong. This is one of the mistakes shown later in this lesson.

A third example: a streak with a dip

Here is one more trace with a mix of rises and falls, to show the stack shrinking and growing. The prices are [3, 1, 2, 4].

• Day 0, price 3. The stack is empty, so the span is 1. Push day 0. The stack is [0].
• Day 1, price 1. The top is day 0 at 3. 3 is higher than 1, so nothing is popped. The span is 1. Push day 1. The stack is [1, 0].
• Day 2, price 2. The top is day 1 at 1. 1 is no higher than 2, so pop it. The next top is day 0 at 3. 3 is higher than 2, so stop. The span is 2 minus 0, which is 2. Push day 2. The stack is [2, 0].
• Day 3, price 4. Pop day 2 at 2, because 2 is no higher than 4. Pop day 0 at 3, because 3 is no higher than 4. The stack is empty, so the span is 3 plus 1, which is 4.

The answers are [1, 1, 2, 4]. The stack went from [0] to [1, 0], then shrank to [2, 0], then emptied.

The full program

The program below has both problems, each with a brute force version, a check of the two against each other on 3000 random lists, and the traces shown above. The trace argument turns on the printed lines. The program prints the lines in the order shown in this lesson. The output was produced with Python 3.14.

The output of the program is below. The trace lines match the traces in the sections above.

temps   [73, 74, 75, 71, 69, 72, 76, 73]
brute   [1, 1, 4, 2, 1, 1, 0, 0]
stack   [1, 1, 4, 2, 1, 1, 0, 0]
trace:
day 0 temp 73 | stack before [] | popped none | stack after [0]
day 1 temp 74 | stack before [0] | popped 0 | stack after [1]
day 2 temp 75 | stack before [1] | popped 1 | stack after [2]
day 3 temp 71 | stack before [2] | popped none | stack after [3, 2]
day 4 temp 69 | stack before [3, 2] | popped none | stack after [4, 3, 2]
day 5 temp 72 | stack before [4, 3, 2] | popped 4 3 | stack after [5, 2]
day 6 temp 76 | stack before [5, 2] | popped 5 2 | stack after [6]
day 7 temp 73 | stack before [6] | popped none | stack after [7, 6]
 
prices  [100, 80, 60, 70, 60, 75, 85]
span    [1, 1, 1, 2, 1, 4, 6]
trace:
day 0 price 100 | stack before [] | popped none | span 1 | stack after [0]
day 1 price 80 | stack before [0] | popped none | span 1 | stack after [1, 0]
day 2 price 60 | stack before [1, 0] | popped none | span 1 | stack after [2, 1, 0]
day 3 price 70 | stack before [2, 1, 0] | popped 2 | span 2 | stack after [3, 1, 0]
day 4 price 60 | stack before [3, 1, 0] | popped none | span 1 | stack after [4, 3, 1, 0]
day 5 price 75 | stack before [4, 3, 1, 0] | popped 4 3 | span 4 | stack after [5, 1, 0]
day 6 price 85 | stack before [5, 1, 0] | popped 5 1 | span 6 | stack after [6, 0]
 
equal prices [5, 5, 5, 3, 5] span [1, 2, 3, 1, 5] brute [1, 2, 3, 1, 5]
warmer   [30, 20, 25, 28, 27, 35] [5, 1, 1, 2, 1, 0]
span     [3, 1, 2, 4] [1, 1, 2, 4]
random lists checked: 3000 mismatches: 0
rising n=1000 brute inner steps 499500
rising n=1000 span first 5 [1, 2, 3, 4, 5]
rising n=1000 stack span first 5 [1, 2, 3, 4, 5]

Common mistakes

Storing values instead of positions. A list of prices or temperatures on the stack cannot give a distance. You need the index to subtract. The fix is to push day, not temps[day], and read the value with temps[waiting[-1]] when you need it.

Reading the top of an empty stack. stack[-1] on an empty list raises an error. Take this short program, which reads the top before checking that the stack has anything on it. The traceback below comes from running it as a file named empty_top.py. The folder and line number in your traceback will be different.

prices = [100, 80, 60]
higher = []
day = 0
print(prices[higher[-1]] <= prices[day])

Traceback (most recent call last):
  File ".../empty_top.py", line 4, in <module>
    print(prices[higher[-1]] <= prices[day])
                 ~~~~~~^^^^
IndexError: list index out of range

The fix is to check if higher before reading the top, as the stock span code does with day + 1 if not higher else day - higher[-1].

Python lists have no peek method, so a stack that calls peek fails in a different way:

AttributeError: 'list' object has no attribute 'peek'

Calling pop on an empty list fails too. The message is IndexError: pop from empty list. The loops in this lesson never call pop on an empty list, because each while line checks that the list is not empty first.

Using < instead of <= in the stock span pop. Equal prices then stay on the stack, and the spans of the equal days are too small. For the prices [5, 5, 5], the correct spans are 1, 2 and 3. The buggy version prints this:

strict pop span [1, 1, 1] correct [1, 2, 3]

Forgetting the plus one for an empty stack in stock span. If the stack is empty, the streak reaches day 0, so the span is day + 1. Writing day gives one less. For the prices [100, 80, 60], the first day should have span 1, but the buggy version prints 0:

off-by-one span [0, 1, 1] correct [1, 1, 1]

Using >= instead of > in the daily temperatures pop. An equal temperature is not warmer, so it must not settle a waiting day. With >=, the answers for equal days come out too small. For the temperatures [73, 73, 74], the correct answers are 2, 1 and 0, because day 0 has to wait until day 2 for a warmer day.

equal-pop warmer [1, 1, 0] correct [2, 1, 0]

Practice

Exercise 1

Trace warmer_with_stack by hand on [30, 20, 25, 28, 27, 35]. Write the answer list.

Show the answer

The answer list is [5, 1, 1, 2, 1, 0]. Day 0 at 30 waits until day 5 at 35, a wait of 5. Day 1 at 20 waits one day for 25. Day 2 at 25 waits one day for 28. Day 3 at 28 waits two days for 35. Day 4 at 27 waits one day for 35. Day 5 has no later day, so its answer is 0.

Exercise 2

Find the stock span for every day of [10, 10, 12, 9, 11]. Remember that equal prices count toward the span.

Show the answer

The spans are [1, 2, 3, 1, 2]. Day 1 at 10 counts day 0 at 10, so its span is 2. Day 2 at 12 counts both earlier days, so its span is 3. Day 3 at 9 is lower than 12, so its span is 1. Day 4 at 11 counts day 3 at 9, but day 2 at 12 is higher, so its span is 2.

Exercise 3

The program for stock span uses prices[higher[-1]] <= prices[day] in the pop condition. Explain, in words a beginner can follow, why this is safe. Then say what the stack holds from bottom to top.

Show the answer

A popped day has a price no higher than today's. Any later day that looks back would reach today before it reached the popped day. Today is closer and at least as high, so the popped day can never be the nearest higher day for anything later. Popping it loses nothing. From bottom to top, the stack holds prices that go down, because a day is pushed only after all lower-or-equal days above it have been removed.

Exercise 4

For daily temperatures, the stack holds positions that are still waiting. Explain why the positions on the stack always have temperatures that go down from bottom to top, and say what this means for the stack at the end of the run.

Show the answer

A new day is pushed only after every waiting day that is cooler than it has been popped. So the day just below it on the stack is at least as warm. Read from bottom to top, the temperatures never go up. At the end of the run, every position still on the stack never saw a warmer day, so its answer stays 0. The stack at the end is the list of days with no warmer future day.

Exercise 5

Compute warmer_with_stack and the brute force on [70, 71, 70, 69, 75]. Then say how many positions are on the stack after day 4 finishes.

Show the answer

Both methods give [1, 3, 2, 1, 0]. Day 0 at 70 waits one day for 71. Day 1 at 71 waits three days for 75. Day 2 at 70 waits two days. Day 3 at 69 waits one day. Day 4 has no warmer day. After day 4 finishes, the stack holds only position 4, because day 4 has not yet been popped.

Summary

• Both problems use one loop: scan once, pop the stack while the top is settled by the new item, then push the new item.
• The stack stores positions, so distances can be computed by subtraction.
• Daily temperatures writes answers when a warmer day pops a waiting day. It needs the future.
• Stock span reads the nearest higher earlier day after popping, so it can run on a live feed.
• The brute force costs O(n squared) on rising prices. The stack costs O(n), because each position is pushed and popped at most once.
• When a result is wrong, check the comparison operator and the empty-stack case first.