Crack the Backend

Problem Statement

You are given an array temperatures where temperatures[i] is the temperature on day i. 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 no future day is warmer, answer[i] = 0.

Key Observations

Monotonic stack (store indices): We keep a stack of indices whose temperatures are in decreasing order (from bottom to top). When we process day i, if temperatures[i] is greater than temperatures[stack.peek()], then the "next warmer day" for the popped index is i — set answer[popped] = i - popped. Pop until stack is empty or top has a temperature >= current; then push i.
Each index is pushed once and popped at most once, so time is O(n).

Approach

High-level: Stack of indices (temps decreasing). For each index i: while stack not empty and temperatures[i] > temperatures[stack.peek()], answer[stack.pop()] = i - popped; push i. Initialize answer with 0s.

Steps: int[] ans = new int[T.length]; Deque<Integer> st; for (int i = 0; i < T.length; i++) { while (!st.isEmpty() && T[i] > T[st.peek()]) { int p = st.pop(); ans[p] = i - p; } st.push(i); } return ans.

Implementation

Java

public int[] dailyTemperatures(int[] T) {
    int[] ans = new int[T.length];
    Deque<Integer> st = new ArrayDeque<>();

    for (int i = 0; i < T.length; i++) {
        while (!st.isEmpty() && T[i] > T[st.peek()]) {
            ans[st.peek()] = i - st.pop();
        }

        st.push(i);
    }

    return ans;
}

Test Cases

Example 1

Input

T = [73,74,75,71,69,72,76,73]

Expected

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

Explanation

Days until warmer.

Complexity Analysis

Time: O(n).
Space: O(n) for stack.

Follow-ups

Previous smaller; range queries.