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, because each day is pushed once and popped at most once. Scanning forward from every day takes O(n²) time, about 5 × 10^7 comparisons for 10^4 days with no warmer day.

Q: Can Daily Temperatures be solved without a stack?

Yes. Fill the answers from the last day back, and for day i start at j = i+1 ; while day j is not warmer, jump to j + answer[j] , the day that answers j . If answer[j] is 0, day i gets 0 too. The jumps skip days that cannot answer i : O(n) time, no extra memory.

MediumMonotonic stack

+10

temperatures[i] is the temperature on day i. For every day, count how many days you wait after it until a strictly warmer day arrives, or 0 if no warmer day comes later. 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 (71) waits 2 days for 72. Day 3 (70) skips the equal 70 on day 4 and waits 2 days for 75. Nothing after 75 or 68 is warmer, so both get 0.

Follow-up

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

Solution

A forward scan from every day repeats work, and when warm days are rare each scan runs to the end. Instead, walk the days once and let each new day answer the earlier days it beats. The days still waiting sit on a stack whose temperatures never rise from bottom to top, so every answer comes in one pass.

Scan forward from every day

Correct, but does not finish on the largest tests

Intuition

For day i, check days i+1, i+2 and so on, and stop at the first strictly warmer day j. The answer is j-i, or 0 if the scan reaches the end. Scanning in order makes the first warmer day you meet the first one there is.

If all 10^4 days have the same temperature, no scan stops early: about n²/2 = 5 × 10^7 comparisons, and day 1 walks almost the same ground day 0 already walked.

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

Keep the days that have no answer yet on a stack, as indices. When today arrives, pop every waiting day colder than today: today is its first warmer day, so its answer is today - day. Then push today.

Only the top needs checking. A day is pushed only after every colder day above it was popped, so the temperatures on the stack never rise from bottom to top. If today is not warmer than the top, it is not warmer than anything below, and you stop popping. In the first example, day 5 (75) pops days 4, 3 and 2 with waits 1, 2 and 3, while the second 70 never popped the first, since equal is not warmer.

Each day is pushed once and popped at most once, so the pops add up to at most n: O(n) time, 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

Popping on >= instead of >. In the first example day 3 then waits 1 day for the second 70 instead of 2 days for 75.
Pushing temperatures instead of indices. You then cannot compute the distance or tell which entry of the answer to fill.
Using if where you need while. One warm day can answer many waiting days: 75 in the first example answers three.
Leaving the days still on the stack unset. Their answer is 0; in C, allocate the answer with calloc, 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.

Frequently asked questions3

What is the time complexity of Daily Temperatures?

The monotonic stack solution runs in O(n) time and O(n) extra space, because each day is pushed once and popped at most once. Scanning forward from every day takes O(n²) time, about 5 × 10^7 comparisons for 10^4 days with no warmer day.

Can Daily Temperatures be solved without a stack?

Yes. Fill the answers from the last day back, and for day i start at j = i+1; while day j is not warmer, jump to j + answer[j], the day that answers j. If answer[j] is 0, day i gets 0 too. The jumps skip days that cannot answer i: O(n) time, no extra memory.

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 stack, flipped to pop on a smaller value, answers next smaller element questions.

def dailyTemperatures(temperatures):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

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