MediumBlind75ArrayStackMonotonic Stack

Daily Temperatures

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.

Examples

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

Day 0 (73): next warmer is day 1 (74), wait 1 day.

Constraints

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

Approaches

For each day, scan forward to find the next warmer day.

CodeT: O(n^2) | S: O(1)
def daily_temperatures(temperatures):
    result = [0] * len(temperatures)
    for i in range(len(temperatures)):
        for j in range(i + 1, len(temperatures)):
            if temperatures[j] > temperatures[i]:
                result[i] = j - i
                break
    return result

Use a stack to keep indices of days with decreasing temperatures.

CodeT: O(n) | S: O(n)
def daily_temperatures(temperatures):
    result = [0] * len(temperatures)
    stack = []
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_index = stack.pop()
            result[prev_index] = i - prev_index
        stack.append(i)
    return result

Traverse from right to left using a stack.

Diagram

temperatures = [73,74,75,71,69,72,76,73] Monotonic stack processes from left to right Result: [1,1,4,2,1,1,0,0]
CodeT: O(n) | S: O(n)
def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and temperatures[stack[-1]] <= temperatures[i]:
            stack.pop()
        if stack:
            result[i] = stack[-1] - i
        stack.append(i)
    return result

Complexity Comparison

Brute Force
T: O(n^2)S: O(1)

For each day, scan forward to find the next warmer day.

Monotonic Stack
T: O(n)S: O(n)

Use a stack to keep indices of days with decreasing temperatures.

Reverse Traversal
T: O(n)S: O(n)

Traverse from right to left using a stack.

Common Mistakes

Using a stack that stores values instead of indices

Not popping elements that are less than or equal to the current temperature

Forgetting to initialize the result array with zeros

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems