Skip to main content

739. Daily Temperatures

medium

For each day, return how many days you'd wait for a warmer temperature. The canonical monotonic-stack problem and gateway to the 'next greater element' family.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Constraints

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

Examples

Example 1

Input
temperatures = [73,74,75,71,69,72,76,73]
Output
[1,1,4,2,1,1,0,0]

Example 2

Input
temperatures = [30,40,50,60]
Output
[1,1,1,0]

Example 3

Input
temperatures = [30,60,90]
Output
[1,1,0]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force is O(n^2) — for each day, scan forward. Won't fit 10^5.

Hint 2

Think 'which previous days are still waiting for a warmer day right now?' That's a stack — of indices, monotonically decreasing in temperature.

Hint 3

Scan left to right. While the stack is non-empty and today's temperature beats the temperature at the index on top, pop that index and write today's distance into answer.

Hint 4

After the inner loop, push today's index. Anything left on the stack at the end has no warmer future day — answer stays 0.

Solution approach

Reveal approach

Monotonic decreasing stack of indices (decreasing by temperature). Scan i from 0 to n-1. While the stack is non-empty and temperatures[stack.top()] < temperatures[i], pop an index j and set answer[j] = i - j. Then push i. Anything remaining on the stack at the end has answer 0 (initialized that way). Each index is pushed and popped at most once, so amortized O(n) time, O(n) space. A right-to-left scan is also possible — try it as an exercise.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack
  • monotonic-stack
  • array

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Bloomberg
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Daily Temperatures and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →