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 Sam K., 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

More Stacks practice problems

See all Stacks problems →