Daily Temperatures

Q: What is the time complexity of Daily Temperatures?

The monotonic stack solution runs in O(n) time and O(n) extra space. Each day is pushed once and popped at most once, so the inner loop runs at most n times over the whole walk. Scanning forward from every day takes O(n²) time, about 5 × 10^7 comparisons for 10^4 days with no warmer day.

Q: Why does the stack store indices instead of temperatures?

The answer for a day is a distance, today - day , so you need the day's position. The index also tells you which entry of the answer array to fill when the day is popped. The temperature is one lookup away as temperatures[day] , so storing it as well adds nothing.

Q: Can Daily Temperatures be solved without a stack?

Yes. Walk from the last day to the first, and for day i start at j = i+1 . While day j is not warmer, jump to the day that answers j , j + answer[j] ; if answer[j] is 0, nothing warmer exists and day i gets 0 too. The jumps skip every day that cannot be the answer, each day gets skipped over at most once, and the time stays O(n) with no memory besides the answer array.

MediumMonotonic stack

+10

You get the temperature of each day in a row of days: temperatures[i] is the temperature on day i. For every day, count how many days you have to wait after it until a strictly warmer day arrives. If no warmer day comes later, the wait for that day is 0.

Return an array of the same length where entry i is the wait for day i.

Function

dailyTemperatures(temperatures: integer-array) → integer-array

temperaturesinteger-array: the temperature of each day, in order
Returnsinteger-array: for each day, the number of days until a warmer one, or 0 if none comes

Constraints

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
Warmer means strictly higher: a later day with the same temperature does not count.

Examples

Input: temperatures = [71, 69, 72, 70, 70, 75, 68]
Output: [2, 1, 3, 2, 1, 0, 0]
Explanation: Day 0 is 71 and the first warmer day is day 2 at 72, so it waits 2 days. Days 3 and 4 are both 70: the second 70 is not warmer, so day 3 waits until day 5 at 75, which is 2 days. Nothing after 75 or 68 is warmer, so both get 0.

+13 hidden tests on Submit

Follow-up

The temperatures take only 71 values, from 30 to 100. How could a table indexed by temperature answer every day in one pass from right to left, and what does that pass cost?

Solution

For one day the answer is a forward scan, but a scan from every day repeats the same work, and when warm days are rare each scan runs to the end of the array. The fix is to let each day answer the earlier days instead of asking about the later ones: a stack of indices that are still waiting, which stays sorted by temperature, gives every answer in a single pass.

Scan forward from every day

Correct, but does not finish on the largest tests

Intuition

Do what the question says. For day i, look at day i+1, then i+2, and so on, and stop at the first day whose temperature is strictly higher. The distance j-i is the answer. If you reach the end without finding one, the answer stays 0.

It is correct because the scan visits the later days in order, so the first warmer day it meets is the first warmer day there is. Stopping right there also matters: a scan that keeps going would record the last warmer day instead.

It is slow when warmer days are far away or missing. If all 10^4 days have the same temperature, no scan ever stops early: day 0 checks 9,999 days, day 1 checks 9,998, and the total is about n²/2 = 5 × 10^7 comparisons. The scans also overlap: day 1 walks almost exactly the ground day 0 already walked and learns nothing from it.

Algorithm

Create an answer array of zeros, one entry per day.
For each day i, scan j from i+1 to the last day.
At the first j with temperatures[j] > temperatures[i], store j-i and stop the scan.
Return the answer array; days whose scan found nothing keep 0.

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i  # the first warmer day, so stop here
                break
    return answer

Monotonic stack of waiting days

Intuition

Flip the question. Instead of asking each day what comes after it, walk the days once and let each new day answer the earlier days it beats. Keep the days that have no answer yet on a stack, as indices. When today arrives, every waiting day that is colder than today has found its first warmer day: today. Pop each of them and write today - day as its answer. Then push today, which now waits for its own warmer day.

Walk through [71, 69, 72, 70, 70, 75, 68]. Day 0 (71) is pushed. Day 1 (69) is not warmer than 71, so it is pushed on top: the stack holds days [0, 1]. Day 2 (72) pops day 1 (wait 1) and then day 0 (wait 2), and is pushed. Days 3 and 4 (70 and 70) are pushed; the second 70 does not pop the first, because equal is not warmer. Day 5 (75) pops day 4 (wait 1), day 3 (wait 2) and day 2 (wait 3). Day 6 (68) is pushed. Days 5 and 6 are still waiting at the end, so they keep 0. The answer is [2, 1, 3, 2, 1, 0, 0].

Why only the top matters: the temperatures on the stack never rise from bottom to top. A day is pushed only after every colder day above it was popped, so everything under it is at least as warm. If today is not warmer than the top, it is not warmer than anything below it either, and you can stop popping. A day leaves the stack the moment the first warmer day shows up, so the wait you record is to the first warmer day, not to the warmest one.

The stack holds indices, not temperatures, because the answer is a distance and because you need to know which entry of the answer to fill. Read the temperature back with temperatures[day]. Each day is pushed once and popped at most once, so all the pops across the whole walk add up to at most n, and the total time is O(n) even though one day can pop many.

Algorithm

Create an answer array of zeros and an empty stack of indices.
For each day today, while the day on top of the stack is colder than today, pop it and set its answer to today minus its index.
Push today onto the stack.
After the loop, the days still on the stack have no warmer day and keep 0. Return the answer array.

def dailyTemperatures(temperatures):
    answer = [0] * len(temperatures)
    waiting = []  # indices of days with no warmer day yet, colder toward the top
    for today, temp in enumerate(temperatures):
        # Today is the first warmer day for every colder day on top of the stack.
        while waiting and temperatures[waiting[-1]] < temp:
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)
    # Days still waiting never get a warmer day and keep their 0.
    return answer

Pitfalls and edge cases

The stack loop is a few lines; the bugs hide in the comparison and in what the stack holds.

Popping on >= instead of >. A day with the same temperature is not warmer. In [71, 69, 72, 70, 70, 75, 68] day 3 waits 2 days for 75, not 1 day for the second 70.
Pushing temperatures instead of indices. The answer is a distance in days, and you need the index to compute it and to know which entry to fill.
Using if where you need while. One warm day can answer many waiting days at once: 75 in the first example answers three.
Returning the warmer temperature or the index of the warmer day. The output is how many days you wait, j-i.
Leaving the days still on the stack unset. Their answer is 0; in C, allocate the answer with calloc or fill it, because malloc memory holds garbage.
Letting the forward scan run past the first warmer day. Without the break it records the last warmer day instead of the first.

Frequently asked questions4

What is the time complexity of Daily Temperatures?

The monotonic stack solution runs in O(n) time and O(n) extra space. Each day is pushed once and popped at most once, so the inner loop runs at most n times over the whole walk. Scanning forward from every day takes O(n²) time, about 5 × 10^7 comparisons for 10^4 days with no warmer day.

Why does the stack store indices instead of temperatures?

The answer for a day is a distance, today - day, so you need the day's position. The index also tells you which entry of the answer array to fill when the day is popped. The temperature is one lookup away as temperatures[day], so storing it as well adds nothing.

Can Daily Temperatures be solved without a stack?

Yes. Walk from the last day to the first, and for day i start at j = i+1. While day j is not warmer, jump to the day that answers j, j + answer[j]; if answer[j] is 0, nothing warmer exists and day i gets 0 too. The jumps skip every day that cannot be the answer, each day gets skipped over at most once, and the time stays O(n) with no memory besides the answer array.

How is Daily Temperatures related to Next Greater Element?

It is the same question asked for every position: find the next larger value to the right. Next Greater Element returns that value; Daily Temperatures returns how far away it is, which is why the stack holds indices. The same monotonic stack, flipped to pop on a smaller value, answers next smaller element questions too.

Python

def dailyTemperatures(temperatures):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

temperatures = [71, 69, 72, 70, 70, 75, 68]

Expected

[2, 1, 3, 2, 1, 0, 0]