Daily Temperatures

This question feels simple. For each day, how long until a warmer day? But the slow answer rescans the future for every single day. The fast answer uses a clever stack that only ever moves forward. This is the question that teaches the monotonic stack pattern.

🎯 The Problem

You get a list of daily temperatures. For each day you answer one thing: how many days until a warmer day arrives?

• Each value in the list is a temperature for one day.
• For each day, count the days you wait until a warmer day shows up.
• Return a list of those waits, one per day.
• If no warmer day ever comes, that day’s answer is 0.

A quick read of [73, 74, 75, 71, 69, 72, 76, 73]. Day 0 is 73. The next day is 74, which is warmer. So the wait is 1. Day 3 is 71. The warmer day is 72 at index 5. So the wait is 2. The last day has nothing warmer ahead, so it is 0.

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

Explanation: each number is how many days until a warmer temperature.

Here is the question drawn for a few days. The arrow points to the next warmer day.

🐢 Approach 1: Look Ahead Every Day (Brute Force)

For each day, scan forward until you hit a warmer day.

The idea:

• Stand on each day in turn.
• Look at every day after it.
• Stop at the first day that is warmer.
• The wait is the gap in days. If none is warmer, the wait is 0.

Why it is weak:

• For each day you may scan most of the rest of the list.
• A list that keeps getting colder forces a near full scan every time.
• Time is O(n²), where n is the number of days. Too slow on a long list.

Here is the look-ahead code:

def daily_temperatures(temperatures):
    answer = [0] * len(temperatures)
    for i in range(len(temperatures)):
        for j in range(i + 1, len(temperatures)):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i
                break
    return answer

⚡ Approach 2: Monotonic Stack (Best)

The idea in one line: keep a stack of days still waiting for warmth, and settle each one the moment a warmer day arrives.

The idea:

• A monotonic stack is a stack kept in one fixed order. Here the temperatures only decrease from bottom to top.
• Store the index of each waiting day, not its temperature. The index lets us measure the gap later.

How it works:

• Walk the days once with their index.
• Compare today with the day on top of the stack.
• While today is warmer than that top day, pop it. Its wait is today’s index minus the popped index.
• Keep popping while today is warmer than the new top. Then push today’s index.

Why it is fast:

• Each index is pushed once and popped at most once.
• So even with the inner loop the total work is O(n).

Here is a dry run on the first few values [73, 74, 75, 71]. Watch the stack of indices change.

Steps to Solve

1. Make an answer list filled with zeros, one slot per day.
2. Make an empty stack to hold indices of waiting days.
3. Walk through the days with their index.
4. While the stack is not empty and today is warmer than the day on top, pop that index and set its answer to today’s index minus the popped index.
5. Push today’s index onto the stack.
6. After the last day, any indices still on the stack keep their answer of zero.

#include <stdio.h>

void dailyTemperatures(int temps[], int n, int answer[]) {
    int stack[100000];  // holds indices of waiting days
    int top = 0;
    for (int i = 0; i < n; i++) {
        answer[i] = 0;  // default wait is zero
    }
    for (int i = 0; i < n; i++) {
        // while today is warmer than the day on top of the stack
        while (top > 0 && temps[i] > temps[stack[top - 1]]) {
            int prev = stack[--top];      // that day's wait is over
            answer[prev] = i - prev;      // gap in days
        }
        stack[top++] = i;                 // today waits for its warmer day
    }
}

int main(void) {
    int temps[] = {73, 74, 75, 71, 69, 72, 76, 73};
    int n = 8;
    int answer[8];
    dailyTemperatures(temps, n, answer);
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", answer[i]);
        if (i + 1 < n) printf(", ");
    }
    printf("]\n");
    return 0;
}

[1, 1, 4, 2, 1, 1, 0, 0]

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> dailyTemperatures(vector<int>& temps) {
    int n = temps.size();
    vector<int> answer(n, 0);  // default wait is zero
    stack<int> st;             // holds indices of waiting days
    for (int i = 0; i < n; i++) {
        while (!st.empty() && temps[i] > temps[st.top()]) {
            int prev = st.top(); st.pop();  // its wait is over
            answer[prev] = i - prev;        // gap in days
        }
        st.push(i);            // today waits for its warmer day
    }
    return answer;
}

int main() {
    vector<int> temps = {73, 74, 75, 71, 69, 72, 76, 73};
    vector<int> answer = dailyTemperatures(temps);
    cout << "[";
    for (size_t i = 0; i < answer.size(); i++) {
        cout << answer[i];
        if (i + 1 < answer.size()) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

[1, 1, 4, 2, 1, 1, 0, 0]

import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Arrays;

public class DailyTemperatures {
    public static int[] dailyTemperatures(int[] temps) {
        int n = temps.length;
        int[] answer = new int[n];           // defaults to all zeros
        Deque<Integer> stack = new ArrayDeque<>();  // indices of waiting days
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temps[i] > temps[stack.peek()]) {
                int prev = stack.pop();      // its wait is over
                answer[prev] = i - prev;     // gap in days
            }
            stack.push(i);                   // today waits
        }
        return answer;
    }

    public static void main(String[] args) {
        int[] temps = {73, 74, 75, 71, 69, 72, 76, 73};
        System.out.println(Arrays.toString(dailyTemperatures(temps)));
    }
}

[1, 1, 4, 2, 1, 1, 0, 0]

def daily_temperatures(temps):
    n = len(temps)
    answer = [0] * n          # default wait is zero
    stack = []                # holds indices of waiting days
    for i in range(n):
        # while today is warmer than the day on top of the stack
        while stack and temps[i] > temps[stack[-1]]:
            prev = stack.pop()        # that day's wait is over
            answer[prev] = i - prev   # gap in days
        stack.append(i)               # today waits for its warmer day
    return answer


temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))

[1, 1, 4, 2, 1, 1, 0, 0]

function dailyTemperatures(temps) {
  const n = temps.length;
  const answer = new Array(n).fill(0); // default wait is zero
  const stack = [];                    // holds indices of waiting days
  for (let i = 0; i < n; i++) {
    while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
      const prev = stack.pop();        // that day's wait is over
      answer[prev] = i - prev;         // gap in days
    }
    stack.push(i);                     // today waits for its warmer day
  }
  return answer;
}

const temps = [73, 74, 75, 71, 69, 72, 76, 73];
console.log(dailyTemperatures(temps));

[
  1, 1, 4, 2,
  1, 1, 0, 0
]

Let us read the Python version line by line and understand why each line is there.

The line answer = [0] * n makes a list of zeros, one per day. Zero is the right default. If a day never finds a warmer day, its answer stays zero. So we never have to handle that case again. The line stack = [] is our pile of waiting day indices. We store indices, not temperatures. We need the index so we can compute the gap later.

The loop for i in range(n) reads each day. The inner while stack and temps[i] > temps[stack[-1]] is the engine. The part stack[-1] peeks at the top index without removing it. temps[stack[-1]] is the temperature of that waiting day. So we keep going while today is warmer than the top waiting day. Inside, prev = stack.pop() removes that index, because today is its warmer day. Then answer[prev] = i - prev records the wait as the gap in days. The while loop can pop several days at once, because today might be warmer than several waiting days.

After the while loop ends, stack.append(i) puts today on the stack. Today now waits for its own warmer day. Each index is pushed once and popped at most once. That is why this reads each day only a couple of times, giving O(n) total.

⏱️ Time and Space Complexity

The brute force rescans the future for each day, so it is O(n²). The monotonic stack pushes and pops each index at most once, so even with the inner while loop the total work is O(n). The stack can hold up to n indices in the worst case, like a list that keeps getting colder. So the space is O(n).

🧩 Key Takeaways

• ✅ For each day you want the number of days until a warmer day, or zero if none.
• ✅ A monotonic stack holds indices of days still waiting for warmth.
• ✅ When today is warmer than the top day, pop it and record the gap in days.
• ✅ Store indices, not temperatures, so you can compute the wait.
• ✅ Each index is pushed and popped once, so the total time is O(n).

🚀 What’s Next?

• Car Fleet
• Evaluate Reverse Polish Notation