Coding problem · Medium · Stack

Daily Temperatures

Medium Algorithms & data structures Seen at Amazon, Meta, Uber

Given an array temperatures, return an array answer such that answer[i] is the number of days you have to wait after day i to get a warmer temperature. If there is no future warmer day, use 0.

Example 1

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

Constraints

1 <= temperatures.length <= 10^5

Hints

Hint 1

Keep a stack of indices whose warmer day hasn't been found yet; their temperatures are decreasing.

Hint 2

When today is warmer than the stack top, today answers that index — pop and record.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(n)

A monotonic decreasing stack of indices: each new temperature pops every colder day before it and fills in their waiting time. Each index is pushed and popped once, so the total work is O(n) despite the inner loop.

Reference solution

function dailyTemperatures(t) {
  const out = new Array(t.length).fill(0);
  const stack = [];
  for (let i = 0; i < t.length; i++) {
    while (stack.length && t[i] > t[stack[stack.length - 1]]) {
      const j = stack.pop();
      out[j] = i - j;
    }
    stack.push(i);
  }
  return out;
}

function dailyTemperatures(t: number[]): number[] {
  const out = new Array<number>(t.length).fill(0);
  const stack: number[] = [];
  for (let i = 0; i < t.length; i++) {
    while (stack.length && t[i] > t[stack[stack.length - 1]]) {
      const j = stack.pop()!;
      out[j] = i - j;
    }
    stack.push(i);
  }
  return out;
}

def daily_temperatures(temperatures: list[int]) -> list[int]:
    out = [0] * len(temperatures)
    stack: list[int] = []
    for i, t in enumerate(temperatures):
        while stack and t > temperatures[stack[-1]]:
            j = stack.pop()
            out[j] = i - j
        stack.append(i)
    return out

<?php

function dailyTemperatures(array $temperatures): array
{
    $out = array_fill(0, count($temperatures), 0);
    $stack = [];
    foreach ($temperatures as $i => $t) {
        while ($stack && $t > $temperatures[end($stack)]) {
            $j = array_pop($stack);
            $out[$j] = $i - $j;
        }
        $stack[] = $i;
    }
    return $out;
}

class Solution {
    public int[] dailyTemperatures(int[] t) {
        int[] out = new int[t.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < t.length; i++) {
            while (!stack.isEmpty() && t[i] > t[stack.peek()]) {
                int j = stack.pop();
                out[j] = i - j;
            }
            stack.push(i);
        }
        return out;
    }
}

Valid Parentheses · Easy
Min Stack · Medium