Skip to main content

22. Daily Temperatures

mediumAsked at Baidu

For each day, report how many days you have to wait until a warmer temperature, or 0 if there is none.

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

Problem

Given an array of integers temperatures representing daily temperatures, return an array answer where answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If no warmer day exists, answer[i] should be 0.

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]

Approaches

1. Brute force forward scan

For each day, walk forward until a warmer day is seen.

Time
O(n^2)
Space
O(1)
const out=Array(temperatures.length).fill(0);
for(let i=0;i<temperatures.length;i++)for(let j=i+1;j<temperatures.length;j++)if(temperatures[j]>temperatures[i]){out[i]=j-i;break;}
return out;

Tradeoff:

2. Monotonic decreasing stack

Walk left to right; pop the stack while today is warmer than the top day, recording the gap. Push today.

Time
O(n)
Space
O(n)
function dailyTemperatures(temperatures) {
  const out = Array(temperatures.length).fill(0);
  const stack = []; // indices with decreasing temperatures
  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length && temperatures[stack[stack.length - 1]] < temperatures[i]) {
      const j = stack.pop();
      out[j] = i - j;
    }
    stack.push(i);
  }
  return out;
}

Tradeoff:

Baidu-specific tips

Baidu uses monotonic stacks to compute next-warmer-bid lookups on ad-ranking streams, so they specifically want the stack pattern and may follow up with the same idea applied to stock-span style problems.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Daily Temperatures and other Baidu interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →