How do you solve Daily Temperatures?

Use a monotonic decreasing stack to store pairs of (temperature, index). Iterate through the temperatures array. For each temperature, pop from the stack while the current temperature is greater than the temperature at the top of the stack. For each popped element, calculate the difference in indices to find how many days to wait. Push the current temperature and index onto the stack. This ensures each element is pushed and popped at most once, resulting in O(n) time complexity.

Daily Temperatures

Q: What is the time complexity of Daily Temperatures?

O(n). Each temperature is pushed onto the stack once and popped at most once, resulting in linear time complexity.

Q: What pattern does Daily Temperatures use?

The Pattern: Monotonic Stack (Next Greater Element) The Heuristic: Maintain a stack of indices whose corresponding values form a strictly decreasing sequence; when a new value breaks this order, pop all smaller elements to resolve their 'next greater' answers immediately, ensuring each element is processed once.

Medium Monotonic Stack

Problem

Given a list of daily temperatures, return a list such that for each day, it tells how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

1 ≤ temperatures.length ≤ 10⁵
30 ≤ temperatures[i] ≤ 100

Example

Input: temperatures = [73,74,75,71,69,72,76,73]

Output: [1,1,4,2,1,1,0,0]

Starting at day 0 with temperature 73, the next warmer day is day 1 with 74, so answer[0] = 1. For day 1 (74), the next warmer day is day 2 (75), so answer[1] = 1. For day 2 (75), the next warmer day is day 6 (76), which is 4 days later, so answer[2] = 4. For day 3 (71), the next warmer day is day 5 (72), so answer[3] = 2. For day 4 (69), the next warmer day is day 5 (72), so answer[4] = 1. For day 5 (72), the next warmer day is day 6 (76), so answer[5] = 1. Days 6 and 7 have no warmer future days, so their answers are 0.

Approach

Straightforward Solution

A brute-force approach checks for each day all future days until a warmer temperature is found, resulting in O(n^2) time complexity, which is too slow for large inputs.

Core Observation

For each day, the answer depends on finding the next day with a strictly higher temperature. This is a classic 'next greater element' problem where the relative order of days matters and we want to efficiently find the next warmer day for each index.

Path to Optimal

Preview

The key recognition signals are 'next warmer day', 'for each element find next greater element', and 'efficient lookup'…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a monotonic decreasing stack to store pairs of (temperature, index). Iterate through the temperatures array…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each temperature is pushed onto the stack once and popped at most once, resulting in linear time complexity.

Space

O(n)

The stack can hold up to all elements in the worst case (strictly decreasing temperatures), and the output array is also O(n), which is required by the problem.

Pattern Spotlight

Monotonic Stack (Next Greater Element)

Maintain a stack of indices whose corresponding values form a strictly decreasing sequence; when a new value breaks this order, pop all smaller elements to resolve their 'next greater' answers immediately, ensuring each element is processed once.

Solution

Python

1class Solution:
  def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
      res = [0] * len(temperatures)
      stack = []
5
      for i, t in enumerate(temperatures):
          while stack and t > stack[-1][0]:
              stack_temp, stack_i = stack.pop()
              res[stack_i] = i - stack_i
          stack.append([t, i])
      
      return res

Step-by-Step Solution

Initialize Result Array and Monotonic Stack

3res = [0] * len(temperatures)
4stack = []

Objective

To prepare the output array with default values and create a stack to track unresolved temperatures.

Key Insight

Initializing the result array with zeros handles the default case where no warmer day exists. The stack will hold pairs of (temperature, index) in decreasing order, enabling efficient resolution of next warmer days as the iteration progresses.

Interview Quick-Check

Core Logic

The result array is pre-filled with zeros to represent days with no warmer future temperature by default.

State & Boundaries

The stack starts empty and will only contain indices of days for which the next warmer day is not yet found.

Iterate Through Temperatures and Resolve Next Warmer Days

To process each day's temperature, updating the result for previous days that find their next warmer day.

Return the Computed Result Array

To output the final array containing the number of days to wait for a warmer temperature for each day.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 7 Critical

while stack and t > stack[-1][0]:

While the stack is not empty and current temperature is warmer than the top of the stack's temperature, pop from stack.

This loop resolves all previous days with temperatures lower than the current one, ensuring that each popped day finds its next warmer day immediately, which is the core of the monotonic stack approach.

Line 9 Critical

res[stack_i] = i - stack_i

Calculate and store the number of days waited for a warmer temperature for the popped day.

The difference between the current index and the popped index gives the exact number of days waited, which is the required output for that day.

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

Why does using a monotonic stack guarantee that each element is processed only once, ensuring O(n) time?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Daily Temperatures from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Daily Temperatures drill

or drill a free problem

1	`class Solution:`
2	`def dailyTemperatures(self, temperatures: list[int]) -> list[int]:`
3	`res = [0] * len(temperatures)`
4	`stack = []`
5
6	`for i, t in enumerate(temperatures):`
7	`while stack and t > stack[-1][0]:`
8	`stack_temp, stack_i = stack.pop()`
9	`res[stack_i] = i - stack_i`
10	`stack.append([t, i])`
11
12	`return res`