DSA problem
Daily Temperatures
Given an integer array temperatures representing the daily temperatures, return an array answer where answer[i] is the number of days you have to wait after day i to get a warmer temperature. If no future day has a warmer temperature, set answer[i] to 0.
The brute force is the obvious double loop: for each day, scan to its right until you find a warmer temperature, costing O(n²) time. That works for tiny inputs but is too slow for n up to 10⁵.
The optimal approach uses a monotonic decreasing stack of indices. As we iterate left-to-right, the stack stores indices whose answer we have not yet computed; the corresponding temperatures decrease from bottom to top. When we see a day i whose temperature exceeds the temperature at the stack's top, we have just discovered the next warmer day for that pending index — pop it and set answer[top] = i - top. We keep popping while the current temperature still beats the new top.
This is the canonical "next greater element on indices" pattern. Each index is pushed exactly once and popped at most once, so the total work is linear despite the inner while loop. Indices that remain on the stack at the end of the iteration have no warmer future day, and their answer stays at the default 0.
Examples
temperatures = [73,74,75,71,69,72,76,73][1,1,4,2,1,1,0,0]temperatures = [30,40,50,60][1,1,1,0]temperatures = [30,60,90][1,1,0]Constraints
- 1 <= temperatures.length <= 10^5
- 30 <= temperatures[i] <= 100
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.