Daily Temperature Threshold — Problem Statement & Solution Guide
Problem Description
Given an integer array temperatures representing the recorded peak temperature for each consecutive day, produce an integer array answer of the same length. For each index i, answer[i] must equal the number of days one must wait after day i to encounter a day j (i<j) with temperatures[j] strictly greater than temperatures[i]. If no such future day exists, set answer[i] to -1. The algorithm should run in linear time relative to the array size.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Daily Temperature Threshold"
WHY DOES IT MATTER?
Monotonic stacks turn a seemingly quadratic "next greater" search into linear time, a pattern that recurs in many interval‑based problems such as stock span, histogram max rectangle, and rain water trapping.
OPTIMIZATION CHALLENGE
The key insight is that once a temperature is lower than a later temperature, it can never be the answer for any earlier day, allowing us to discard it permanently from the stack.
REAL-WORLD CONNECTION
Think of a conveyor belt of temperature sensors where each sensor waits for a hotter sensor downstream; the stack acts like a line of waiting sensors that get resolved as soon as a hotter reading arrives, similar to back‑pressure handling in streaming pipelines.
During an interview, push indices onto the stack, not values; this lets you compute the exact distance (i - poppedIndex) without extra bookkeeping.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem is a classic monotonic stack scenario where we need to find the next greater element for each position in a linear array. A naive scan from each index i to the right would be O(n^2) and quickly becomes infeasible for large n because it repeats work for overlapping suffixes. By maintaining a stack of indices whose next greater temperature has not yet been discovered, we can process the array in a single left‑to‑right pass: when the current temperature exceeds the temperature at the stack's top index, we pop that index and record the distance, guaranteeing each element is pushed and popped at most once. This yields an overall linear time algorithm while using O(n) auxiliary space for the stack and answer array.
Interview Questions on This Problem
Q1How would you modify the solution if the requirement changed from "strictly greater" to "greater than or equal"?
Replace the strict comparison with a non‑strict one (>=) when checking the stack top; this ensures that equal temperatures are also considered as a valid future day, and the same monotonic decreasing stack logic still applies.
Q2Can you solve the problem in O(1) extra space without using an explicit stack?
Yes, by iterating from right to left and using the answer array itself as a jump pointer: for each i, repeatedly jump to answer[next] until a higher temperature is found or -1 is reached, achieving amortized O(n) time and O(1) extra space.
Q3Why is a monotonic decreasing stack preferred over a priority queue for this problem?
A priority queue would give O(log n) insertion and removal, inflating the overall complexity, whereas a monotonic stack guarantees O(1) amortized operations because each element is pushed and popped exactly once, preserving linear time.
Examples
Input
[30,40,35,38,33,42,31]
Output
[1,4,1,2,1,-1,-1]
Explanation: Day0 (30): first higher temperature is day1 (40) → distance 1. Day1 (40): next higher is day5 (42) → distance 4. Day2 (35): next higher is day3 (38) → distance 1. Day3 (38): next higher is day5 (42) → distance 2. Day4 (33): next higher is day5 (42) → distance 1. Day5 (42): no higher temperature later → -1. Day6 (31): no higher temperature later → -1.
Input
[55,50,60,45,70]
Output
[2,1,2,1,-1]
Explanation: Day0 (55): first higher is day2 (60) → distance 2. Day1 (50): first higher is day2 (60) → distance 1. Day2 (60): first higher is day4 (70) → distance 2. Day3 (45): first higher is day4 (70) → distance 1. Day4 (70): no higher later → -1.
Input
[10,9,8,7]
Output
[-1,-1,-1,-1]
Explanation: All temperatures are decreasing, so no future day has a higher temperature for any index; each entry is -1.
Constraints
- 1 <= temperatures.length <= 200000
- -100 <= temperatures[i] <= 100
- All calculations fit in 32-bit signed integer
- Expected time complexity O(n) and auxiliary space O(n)
Optimal Approach & Strategy
Use a monotonic decreasing stack to process the array in one pass, popping indices whose next greater temperature is the current day and recording distances.
Brute Force Approach
For each day i, scan forward j=i+1..n‑1 until a higher temperature is found; record j‑i or -1 if none exists.
Verified Code Solutions
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 dailyTemperatureThreshold(temperatures) {
const n = temperatures.length;
const answer = new Array(n).fill(-1);
const stack = []; // will store indices with decreasing temperatures
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 result = dailyTemperatureThreshold(temperatures);
console.log(result.join(' '));#include <bits/stdc++.h>
using namespace std;
vector<int> dailyTemperatureThreshold(const vector<int>& temperatures) {
int n = temperatures.size();
vector<int> answer(n, -1);
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);
}
// remaining indices already have -1
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 = dailyTemperatureThreshold(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[] dailyTemperatureThreshold(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
Arrays.fill(answer, -1);
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 IOException {
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];
if (n > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
temps[i] = Integer.parseInt(st.nextToken());
}
}
int[] ans = dailyTemperatureThreshold(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 dailyTemperatureThreshold(temperatures):
n = len(temperatures)
answer = [-1] * n
stack = [] # indices with decreasing temperatures
for i, temp in enumerate(temperatures):
while stack and temp > 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 = dailyTemperatureThreshold(temps)
print(' '.join(map(str, ans)))
if __name__ == "__main__":
main()
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 dailyTemperatureThreshold(temperatures) {
const n = temperatures.length;
const answer = new Array(n).fill(-1);
const stack = []; // will store indices with decreasing temperatures
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 result = dailyTemperatureThreshold(temperatures);
console.log(result.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.