Daily Temperatures — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Stack and solve the Daily Temperatures problem optimally.
O(n)O(n)Problem Description
You are given an integer array temperatures of length n, where temperatures[i] denotes the temperature recorded on day i. For each day i, determine how many days you must wait until a future day j (i < j) with a strictly higher temperature occurs. If such a day does not exist, the answer for day i is 0. Return the resulting array answer of length n.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Daily Temperatures"
WHY DOES IT MATTER?
The monotonic stack pattern solves many "next greater element" queries efficiently, turning quadratic scans into linear passes—a skill frequently tested in system design and algorithmic interviews.
OPTIMIZATION CHALLENGE
The key insight is that once a temperature is lower than a future temperature, it can never be the answer for any earlier day, so it can be discarded immediately, reducing both time and space.
REAL-WORLD CONNECTION
Think of a server load balancer that needs to know when a higher traffic spike will occur; maintaining a decreasing stack of recent loads lets it predict the next surge without scanning the entire log each time.
When coding, process the array once and push indices onto a stack; whenever the current temperature exceeds the stack's top, pop and compute the distance—this avoids nested loops and keeps the code clean.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem asks for the distance to the next greater temperature for each day. A naïve double‑loop scans every later day for each index, leading to O(n²) time which explodes for large n (up to 10⁵). The optimal solution relies on a monotonic decreasing stack: we traverse the array from left to right (or right to left) and keep indices whose temperatures have not yet found a warmer day. When a higher temperature appears, we pop all lower temperatures from the stack, compute their waiting days, and push the current index. This yields a single pass, guaranteeing O(n) time while using O(n) auxiliary space for the stack.
Interview Questions on This Problem
Q1How would you adapt the solution to return the index of the next warmer day instead of the distance?
Store the index directly when you pop from the stack; the answer for that popped index becomes currentIndex - poppedIndex, and you can also keep the popped index as the next warmer day if needed.
Q2Can you solve the problem in O(1) extra space?
Yes, by iterating from right to left and reusing the answer array as a jump pointer, you can achieve O(1) auxiliary space while still maintaining O(n) time.
Q3What changes are needed if temperatures can be equal and you must find the next strictly higher temperature?
The monotonic stack must remain strictly decreasing; when encountering an equal temperature you treat it as not higher, so you push its index onto the stack without popping equal values.
Examples
Input
[30,40,50,60]
Output
[1,1,1,0]
Explanation: Day 0 (30) → next higher is day 1 (40), wait 1 day. Day 1 (40) → next higher is day 2 (50), wait 1 day. Day 2 (50) → next higher is day 3 (60), wait 1 day. Day 3 (60) has no warmer future day, so 0.
Input
[55,53,54,52,58,57]
Output
[4,1,2,1,0,0]
Explanation: Day 0 (55) → first warmer day is day 4 (58), wait 4 days. Day 1 (53) → day 2 (54) is warmer, wait 1 day. Day 2 (54) → day 4 (58) is warmer, wait 2 days. Day 3 (52) → day 4 (58) is warmer, wait 1 day. Day 4 (58) and day 5 (57) have no warmer future days, so both are 0.
Input
[80,80,80]
Output
[0,0,0]
Explanation: All temperatures are equal; no day has a strictly higher temperature later, so every entry is 0.
Constraints
- 1 <= temperatures.length <= 100000
- -1000000000 <= temperatures[i] <= 1000000000
- All elements of temperatures are integers
Optimal Approach & Strategy
Maintain a monotonic decreasing stack of indices while iterating once through the array; pop lower temperatures when a higher one appears, compute distances, and push the current index. This runs in O(n) time.
Brute Force Approach
For each day i, scan forward j=i+1…n‑1 until you find a temperature higher than temperatures[i]; record j‑i or 0 if none is found. This double loop is O(n²).
Code Solutions
'use strict';
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let pos = 0;
const n = data[pos++]||0;
const temperatures = data.slice(pos, pos+n);
function dailyTemperatures(temperatures){
const n = temperatures.length;
const answer = new Array(n).fill(0);
const stack = []; // stores indices
for(let i=0;i<n;i++){
while(stack.length && temperatures[i] > temperatures[stack[stack.length-1]]){
const idx = stack.pop();
answer[idx] = i - idx;
}
stack.push(i);
}
return answer;
}
const ans = dailyTemperatures(temperatures);
console.log(ans.join(' '));#include <bits/stdc++.h>
using namespace std;
vector<int> dailyTemperatures(const vector<int>& temperatures) {
int n = temperatures.size();
vector<int> answer(n,0);
stack<int> st; // stores indices with decreasing temperatures
for(int i=0;i<n;++i){
while(!st.empty() && temperatures[i] > temperatures[st.top()]){
int idx = st.top(); st.pop();
answer[idx] = i - idx;
}
st.push(i);
}
return answer;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> temps(n);
for(int i=0;i<n;++i) cin>>temps[i];
vector<int> ans = dailyTemperatures(temps);
for(size_t i=0;i<ans.size();++i){
if(i) cout << ' ';
cout << ans[i];
}
cout << '\n';
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // stores indices with decreasing temps
for(int i=0;i<n;i++){
while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
int idx = stack.pop();
answer[idx] = i - idx;
}
stack.push(i);
}
return answer;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if(line==null||line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
int[] temps = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) temps[i]=Integer.parseInt(st.nextToken());
int[] ans = dailyTemperatures(temps);
StringBuilder sb = new StringBuilder();
for(int i=0;i<ans.length;i++){
if(i>0) sb.append(' ');
sb.append(ans[i]);
}
System.out.println(sb.toString());
}
}import sys
def dailyTemperatures(temperatures):
n = len(temperatures)
answer = [0]*n
stack = [] # indices with decreasing temps
for i, t in enumerate(temperatures):
while stack and t > temperatures[stack[-1]]:
idx = stack.pop()
answer[idx] = i - idx
stack.append(i)
return answer
def main():
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
temps = list(map(int, data[1:1+n]))
ans = dailyTemperatures(temps)
print(' '.join(map(str, ans)))
if __name__ == "__main__":
main()'use strict';
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let pos = 0;
const n = data[pos++]||0;
const temperatures = data.slice(pos, pos+n);
function dailyTemperatures(temperatures){
const n = temperatures.length;
const answer = new Array(n).fill(0);
const stack = []; // stores indices
for(let i=0;i<n;i++){
while(stack.length && temperatures[i] > temperatures[stack[stack.length-1]]){
const idx = stack.pop();
answer[idx] = i - idx;
}
stack.push(i);
}
return answer;
}
const ans = dailyTemperatures(temperatures);
console.log(ans.join(' '));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.