Daily Temperatures

Why it belongs on this sheet

This is the entry point to monotonic stack problems, and that pattern comes up often in OAs and interviews.

Pattern

Decreasing stack of indices

Approach

Keep indices of days with unresolved warmer temperatures in a stack. When the current day is warmer than the top index, resolve that earlier day and continue popping.

Java solution

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

class Solution {
  public int[] dailyTemperatures(int[] temperatures) {
    int[] answer = new int[temperatures.length];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < temperatures.length; i++) {
      while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
        int previousIndex = stack.pop();
        answer[previousIndex] = i - previousIndex;
      }
      stack.push(i);
    }

    return answer;
  }
}

Complexity

• Time: O(n)
• Space: O(n)

Interview note

Store indices, not temperatures, so the waiting distance is easy to compute.