IntermediateStacks & QueuesArrays
Daily Temperatures
Problem
Given an array temperatures where temperatures[i] is the temperature on day i, return an array answer where answer[i] is the number of days you have to wait after day i to get a strictly warmer temperature. If there is no future day with a warmer temperature, answer[i] should be 0.
Constraints
- 1 ≤ n ≤ 10^5
- 30 ≤ temperatures[i] ≤ 100
Examples
in: temperatures = [73,74,75,71,69,72,76,73]
out: [1,1,4,2,1,1,0,0]
in: temperatures = [30,40,50,60]
out: [1,1,1,0]
What this tests
- Recognising the "next greater element" shape
- Monotonic stack of indices and its invariant
- Amortised O(n) argument (each index pushed and popped once)
- Using the tiny value range for an alternative solution
Pattern RecognitionOptimizationComplexity AnalysisImplementation
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Hint 1Direction
Hint 2Pattern
Hint 3Data structure
Hint 4Algorithm
Hint 5Pseudocode
Solution
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Solve in
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
F1
Solve it in
O(1) extra space beyond the output array.F2
Return the *previous* warmer day instead of the next one.
F3
Temperatures arrive as a stream and you must output the answer for a day as soon as it is known.
F4
How would you find, for each day, the number of warmer days in the next
w days?