Daily Temperature Threshold — Problem Statement & Solution Guide
Problem Description
You are given an array of integers temperatures representing daily peak temperatures. For each day, determine the number of days until a day with a higher temperature arrives. If no such day exists, return -1.
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 and for each day, we find the next day with a higher temperature. For the first day (73), the next day with a higher temperature is the second day (74), so the output is 1. We repeat this process for each day.
Input
[89, 62, 70, 58, 59, 90, 75, 85, 73]
Output
[8, 1, 5, 4, 2, 1, 1, 0, 0]
Explanation: Step-by-step: with input [89, 62, 70, 58, 59, 90, 75, 85, 73], we iterate through the array and for each day, we find the next day with a higher temperature. For the first day (89), the next day with a higher temperature is the sixth day (90), so the output is 8.
Constraints
- 1 <= n <= 10^5
- 1 <= arr[i] <= 10^9
Optimal Approach & Strategy
Iterate from right to left. Use a stack. While stack not empty and top is <= current element, pop. If stack is empty, answer is -1. Else, answer is stack top. Push current element. Time O(N), Space O(N).
Brute Force Approach
For each element, scan the rest of the array. Time O(N^2).
Verified Code Solutions
function dailyTemperatures(temperatures) {
const result = new Array(temperatures.length).fill(0);
const stack = [];
for (let i = 0; i < temperatures.length; i++) {
while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const index = stack.pop();
result[index] = i - index;
}
stack.push(i);
}
return result;
}class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> result(temperatures.size(), 0);
stack<int> st;
for (int i = 0; i < temperatures.size(); i++) {
while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
int index = st.top();
st.pop();
result[index] = i - index;
}
st.push(i);
}
return result;
}
};class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] result = new int[temperatures.length];
java.util.Stack<Integer> stack = new java.util.Stack<>();
for (int i = 0; i < temperatures.length; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int index = stack.pop();
result[index] = i - index;
}
stack.push(i);
}
return result;
}
}def dailyTemperatures(temperatures):
result = [0] * len(temperatures)
stack = []
for i in range(len(temperatures)):
while stack and temperatures[i] > temperatures[stack[-1]]:
index = stack.pop()
result[index] = i - index
stack.append(i)
return resultfunction dailyTemperatures(temperatures) {
const result = new Array(temperatures.length).fill(0);
const stack = [];
for (let i = 0; i < temperatures.length; i++) {
while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const index = stack.pop();
result[index] = i - index;
}
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.