Daily Temperatures

medium array stack monotonic

Problem

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you 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. For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Inputtemps = [70, 73, 71, 75, 69, 72]

Output[1, 2, 1, 0, 1, 0]

Day 0 (70) → next warmer is day 1 (73), wait 1. Day 3 (75) has no warmer day after it, so 0.

temperatures (comma-separated)

def daily_temperatures(temps):
    ans = [0] * len(temps)
    stack = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

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

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

vector<int> dailyTemperatures(vector<int>& temps) {
    vector<int> ans(temps.size(), 0);
    stack<int> st;
    for (int i = 0; i < (int)temps.size(); i++) {
        while (!st.empty() && temps[st.top()] < temps[i]) {
            int j = st.top(); st.pop();
            ans[j] = i - j;
        }
        st.push(i);
    }
    return ans;
}

Explanation

For each day we want to know how many days until it gets warmer. The brute-force way would re-scan the future for every day, which is slow. The trick is a monotonic stack of indices of days still waiting for a warmer day.

We walk left-to-right. The stack holds indices of past days whose answer is not yet known, and their temperatures are in decreasing order from bottom to top. When the current day i is warmer than the day on top of the stack, that day's wait is finally over.

So while temps[stack[-1]] < t, we pop that index j and set ans[j] = i - j (the number of days waited). We keep popping every cooler day the current temperature resolves, then push i onto the stack.

Example: temps = [70, 73, 71, 75, 69, 72]. Day 0 (70) is on the stack; day 1 (73) is warmer, so ans[0] = 1. Day 2 (71) waits, day 3 (75) resolves it with ans[2] = 1 and also day 1 with ans[1] = 2. Days left on the stack at the end keep their default 0.

Every index is pushed and popped at most once, so the whole thing runs in linear time despite the inner loop.

Time: O(n) amortised Space: O(n)