Daily Temperature Variations ā Problem Statement & Solution Guide
Problem Description
Given a list of daily temperatures, return a list of the number of days until a warmer temperature occurs. If no warmer temperature occurs, return 0 for that day.
Examples
Input
[73, 74, 75, 71, 69, 72, 76, 73]
Output
[1, 1, 4, 2, 1, 1, 0, 0]
Explanation: Step-by-step: For the given input [73, 74, 75, 71, 69, 72, 76, 73], we start from the first element 73. The next warmer day is 74, so the answer is 1. Then for 74, the next warmer day is 75, so the answer is 1. Then for 75, the next warmer day is 76, so the answer is 1. Then for 76, there is no warmer day, so the answer is 0. We continue this process for each day.
Input
[89, 62, 70, 58, 59, 90, 75, 85, 73, 72, 60, 74]
Output
[1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 0]
Explanation: Step-by-step: For the given input [89, 62, 70, 58, 59, 90, 75, 85, 73, 72, 60, 74], we start from the first element 89. The next warmer day is 90, so the answer is 1. Then for 90, there is no warmer day, so the answer is 0. We continue this process for each day.
Constraints
- Array size ā¤ 10^5
- All temperatures are between -10^8 and 10^8
- No duplicate temperatures in the array
- All elements in the array are integers
Optimal Approach & Strategy
We can use a monotonic stack to optimize the solution. The stack will store the indices of the temperatures. Whenever a warmer temperature is found, we pop the stack and update the result array. This approach reduces the time complexity to O(n).
Brute Force Approach
One possible approach is to iterate through the array for each element and find the next warmer day by comparing with all the following elements. However, this approach has a time complexity of O(nĀ²) due to the nested loops.
Verified Code Solutions
function dailyTemperatures(temperatures) {
const n = temperatures.length;
const stack = [];
const result = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const top = stack.pop();
result[top] = i - top;
}
stack.push(i);
}
return result;
}class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] result = new int[temperatures.length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < temperatures.length; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int last_index = stack.pop();
result[last_index] = i - last_index;
}
stack.push(i);
}
return result;
}
}def dailyTemperatures(temperatures):
stack = []
result = [0] * len(temperatures)
for i in range(len(temperatures)):
while stack and temperatures[i] > temperatures[stack[-1]]:
last_index = stack.pop()
result[last_index] = i - last_index
stack.append(i)
return resultfunction dailyTemperatures(temperatures) {
const n = temperatures.length;
const stack = [];
const result = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const top = stack.pop();
result[top] = i - top;
}
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.