MediumStackArrayUpdated Sep 2026

739. Daily Temperatures

Asked at Google, Meta, Amazon, Microsoft and 4 more

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Stack

Companies

8

Problem

You are given an array temperatures, where temperatures[i] is the temperature on day i. For each day, you want to know how many days you must wait until a strictly warmer day arrives.

Return an array answer of the same length. answer[i] is the number of days between day i and the next day whose temperature is higher than temperatures[i]. If no warmer day ever comes, set answer[i] = 0.

Note that "warmer" means strictly greater. A day with the same temperature does not count, so you keep looking further ahead.

How many days until it gets warmer

temperatures4 days737475716972767301234567Day 2 is 75; the next warmer day is day 6 (76), so answer[2] = 4answer1142110001234567The last two days never see a warmer day, so they stay 0
For each day, look forward to the first strictly higher temperature and count the gap; if none exists, the answer is 0.

Constraints

  • ●1 <= temperatures.length <= 10^5
  • ●30 <= temperatures[i] <= 100

Examples

Example 1
Inputtemperatures = [73,74,75,71,69,72,76,73]
Output[1,1,4,2,1,1,0,0]
WhyDay 0 (73) waits 1 day for 74. Day 2 (75) waits 4 days for 76. Day 3 (71) waits 2 days for 72. The last two days never see anything warmer, so they stay 0.
Example 2
Inputtemperatures = [30,40,50,60]
Output[1,1,1,0]
WhyEach day is followed by a warmer day right away, so the first three answers are 1. The final day has no future day at all, so it is 0.
Example 3
Inputtemperatures = [30,60,90]
Output[1,1,0]
WhyDay 0 waits 1 day for 60, day 1 waits 1 day for 90. Day 2 is the hottest and the last, so its answer is 0.

Asked At

8 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
UberMediumView all Uber questions →
Goldman SachsMediumView all Goldman Sachs questions →
AndurilMediumView all Anduril questions →

How to Think About It

1

Brute force checks every future day for each day — O(n²). The monotonic stack approach brings it to O(n).

2

Use a monotonic decreasing stack storing indices (not values). The stack holds days that haven't found a warmer day yet.

3

When you encounter a warmer day, pop all cooler days from the stack and record the distance. Each index is pushed and popped at most once.

4

Why it works: the stack maintains days in decreasing temperature order. A warmer day "resolves" all previous cooler days.

5

Edge cases: all same temperature (all zeros), strictly increasing (all ones), strictly decreasing (all zeros except last).

Optimal Approach

Step 1: Create result array of size n, fill with 0.
Step 2: Use a stack to store indices.
Step 3: For each day i:
While stack is not empty and temperatures[i] > temperatures[stack[-1]]:
j = stack.pop()
result[j] = i - j
Push i onto stack.
Step 4: Remaining indices in stack already have result[j] = 0.

Each index is pushed once and popped once, giving O(n) time.

Time: O(n). Space: O(n).

Monotonic stack of waiting days

stack (indices)2 (75)3 (71)4 (69)← topBefore day 5: days 2, 3, 4 are still waiting, withtemperatures going downstack (indices)2 (75)5 (72)← topDay 5 is 72: it pops day 4 (answer 1) and day 3(answer 2), then pushes itselfstack (indices)6 (76)← topDay 6 is 76: it pops day 5 (answer 1) and day 2(answer 4), leaving only itselfwhile stack and temp[i] > temp[stack.top]: j = stack.pop(); answer[j] = i - jpush i
The stack keeps days still waiting for warmth, in decreasing temperature order; a warmer day pops and resolves them.
ComplexityTime O(n)Space O(n)Each index is pushed and popped from the stack at most once, and the stack plus the result array can hold up to n entries.

What Trips People Up in Real Interviews

1

Using brute force O(n²). The monotonic stack approach is O(n) and is what the interviewer expects.

2

Storing values in the stack instead of indices. You need indices to compute the answer (difference in positions).

3

Not handling the case where no warmer day exists. The answer for that day is 0 (already initialized).

4

Forgetting that the stack might not be empty after the loop. Remaining indices already have result = 0.

5

Using a monotonic INCREASING stack instead of decreasing. You need a decreasing stack so that when you find a warmer day, it resolves all previous cooler days. An increasing stack never pops.

Solution Code

O(n) time
def dailyTemperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Daily Temperatures problem?

Given an array of integers temperatures represents the daily temperatures, return an array answer such that `answer[i]` is the number of days you have to wait after the ith day to get a warmer temperature.

How do you solve Daily Temperatures?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Daily Temperatures?

Daily Temperatures is asked at Google, Meta, Amazon, Microsoft, Apple, Uber, Goldman Sachs, Anduril. It is a medium difficulty problem.

What are common mistakes on Daily Temperatures?
  • Using brute force `O(n²)`. The monotonic `stack` approach is `O(n)` and is what the interviewer expects.
  • Storing values in the `stack` instead of indices. You need indices to compute the answer (difference in positions).
  • Not handling the case where no warmer day exists. The answer for that day is 0 (already initialized).
  • Forgetting that the stack might not be empty after the loop. Remaining indices already have `result = 0`.
  • Using a monotonic INCREASING `stack` instead of decreasing. You need a decreasing `stack` so that when you find a warmer day, it resolves all previous cooler days. An increasing `stack` never pops.