Daily Temperatures — Problem Statement & Solution Guide
Problem Description
Given an array of integers temperatures representing daily temperatures, find the number of days until a warmer temperature occurs for each day. If no warmer temperature occurs, output 0.
Examples
Input
[73, 74, 75, 71, 69, 72, 76, 73]
Output
[1, 1, 4, 2, 1, 1, 0, 0]
Explanation: Step-by-step: with input [73, 74, 75, 71, 69, 72, 76, 73], we iterate through the array. For the first day (73), the next warmer day is the second day (74), so the output for the first day is 1. For the second day (74), the next warmer day is the third day (75), so the output for the second day is 1. We continue this process for all days.
Input
[89, 62, 70, 58, 59, 90, 75, 85, 73]
Output
[8, 1, 5, 4, 3, 0, 1, 0, 0]
Explanation: Step-by-step: with input [89, 62, 70, 58, 59, 90, 75, 85, 73], we iterate through the array. For the first day (89), we need to find the next warmer day, which is the sixth day (90), so the output for the first day is 8. For the second day (62), the next warmer day is the third day (70), so the output for the second day is 1.
Constraints
- 1 <= n <= 10^5
- 30 <= temp[i] <= 100
Optimal Approach & Strategy
Iterate from left to right. Maintain a monotonic decreasing stack of indices. If current temp > temp[stack top], pop top, answer[top] = current index - top. Time O(N), Space O(N).
Brute Force Approach
For each day, scan future days. Time O(N^2).
Verified Code Solutions
function dailyTemperatures(temperatures) { let stack = [], result = new Array(temperatures.length).fill(0); for (let i = 0; i < temperatures.length; i++) { while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) { let lastIndex = stack.pop(); result[lastIndex] = i - lastIndex; } stack.push(i); } return result; }class Solution { public: vector<int> dailyTemperatures(vector<int>& temperatures) { int n = temperatures.size(); vector<int> result(n, 0); stack<int> st; for (int i = 0; i < n; i++) { while (!st.empty() && temperatures[i] > temperatures[st.top()]) { int lastIndex = st.top(); st.pop(); result[lastIndex] = i - lastIndex; } st.push(i); } return result; } };class Solution { public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] result = new int[n]; java.util.Stack<Integer> stack = new java.util.Stack<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int lastIndex = stack.pop(); result[lastIndex] = i - lastIndex; } stack.push(i); } return result; } }def dailyTemperatures(temperatures): stack, result = [], [0] * len(temperatures); for i, temp in enumerate(temperatures): while stack and temp > temperatures[stack[-1]]: lastIndex = stack.pop(); result[lastIndex] = i - lastIndex; stack.append(i); return resultfunction dailyTemperatures(temperatures) { let stack = [], result = new Array(temperatures.length).fill(0); for (let i = 0; i < temperatures.length; i++) { while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) { let lastIndex = stack.pop(); result[lastIndex] = i - lastIndex; } stack.push(i); } return result; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.