Log inSign up
mediumLeetCodeNot Started

Daily Temperatures

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on LeetCode
Lesson

Problem Statement

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1 · Standard Test Case:

Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Explanation: Day 0 (73) warms on Day 1 (74) -> diff = 1. Day 2 (75) warms on Day 6 (76) -> diff = 4. Day 6 & 7 have no warmer future days -> 0.

Example 2 · Monotonically Decreasing Temperatures:

Input: temperatures = [30, 40, 50, 60]
Output: [1, 1, 1, 0]
Explanation: Each day is strictly warmer than the previous day except the last one.

Example 3 · Strictly Decreasing:

Input: temperatures = [30, 60, 90]
Output: [1, 1, 0]
Explanation: Each consecutive day is warmer.

Constraints:

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why storing indices instead of values in the monotonic stack allows instant distance calculation.
  • Recognize that every index is pushed and popped at most once, providing guaranteed O(N) runtime.
  • Formulate both forward-scan and backward-scan monotonic stack variations.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • Maintain a stack of indices whose next warmer day has not yet been found.
  • Stack stays monotonically decreasing in value from bottom to top.
  • When encountering temperatures[i] > temperatures[st.top()], pop st.top() and record answer[st.top()] = i - st.top().

Connected Patterns:

Next Greater Element INext Greater Element IIOnline Stock Span

1. Nested Loops Search

Intuition

For each day i, scan forward to find the first index j > i where temperatures[j] > temperatures[i] and record j - i.

Algorithm

  1. Step 1: Initialize an answer array ans of size N filled with 0.
  2. Step 2: Loop i from 0 to N - 1.
  3. Step 3: Inside, loop j from i + 1 to N - 1.
  4. Step 4: If temperatures[j] > temperatures[i], set ans[i] = j - i and break inner loop.
  5. Step 5: Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
7 int n = temperatures.size();
8 std::vector<int> ans(n, 0);
9 for (int i = 0; i < n; i++) {
10 for (int j = i + 1; j < n; j++) {
11 if (temperatures[j] > temperatures[i]) {
12 ans[i] = j - i;
13 break;
14 }
15 }
16 }
17 return ans;
18 }
19};
20
21int main() {
22 Solution solver;
23 std::vector<int> temps = {73, 74, 75, 71, 69, 72, 76, 73};
24 std::vector<int> ans = solver.dailyTemperatures(temps);
25 std::cout << "Output: [";
26 for (size_t i = 0; i < ans.size(); i++) {
27 std::cout << ans[i] << (i + 1 < ans.size() ? ", " : "");
28 }
29 std::cout << "]" << std::endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N^2) — For each day i, we check all subsequent days j > i in the worst case (e.g. strictly decreasing temperatures), taking O(N2) total comparisons.
  • Space complexity: O(1) — O(1) extra auxiliary space beyond the output array.

Why Brute Force Doesn't Scale:

A strictly decreasing sequence of 100,000 elements requires ~5 * 109 comparisons.

At N = 100,000, Monotonic Stack finishes in ~10ms compared to several seconds for O(N2).

2. Right-to-Left Monotonic Stack

Intuition

Processing from right to left ensures that the stack always contains the candidates to the right of current day. Pop anything <= current temperature.

Algorithm

  1. Step 1: Initialize stack st and answer array ans of size N.
  2. Step 2: Loop i from N - 1 down to 0.
  3. Step 3: While stack is not empty and temperatures[st.top()] <= temperatures[i], pop stack.
  4. Step 4: If stack is not empty, ans[i] = st.top() - i. Otherwise ans[i] = 0.
  5. Step 5: Push i onto stack.
  6. Step 6: Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4
5class Solution {
6public:
7 std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
8 int n = temperatures.size();
9 std::vector<int> ans(n, 0);
10 std::stack<int> st;
11 for (int i = n - 1; i >= 0; i--) {
12 while (!st.empty() && temperatures[st.top()] <= temperatures[i]) {
13 st.pop();
14 }
15 if (!st.empty()) {
16 ans[i] = st.top() - i;
17 }
18 st.push(i);
19 }
20 return ans;
21 }
22};
23
24int main() {
25 Solution solver;
26 std::vector<int> temps = {73, 74, 75, 71, 69, 72, 76, 73};
27 std::vector<int> ans = solver.dailyTemperatures(temps);
28 std::cout << "Output: [";
29 for (size_t i = 0; i < ans.size(); i++) {
30 std::cout << ans[i] << (i + 1 < ans.size() ? ", " : "");
31 }
32 std::cout << "]" << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) — Iterate from right to left (N-1 down to 0). Each index is pushed and popped at most once.
  • Space complexity: O(N) — O(N) space for maintaining the stack of indices.

3. Optimal Forward Monotonic Stack

Intuition

Scan left to right. Keep unresolved indices on stack. As soon as a warmer temperature is encountered, it resolves the answer for all smaller temperatures currently on the stack top.

Algorithm

  1. Step 1: Initialize ans array of size n with all 0s and an empty stack st.
  2. Step 2: Loop i from 0 to n - 1.
  3. Step 3: While stack is not empty and temperatures[i] > temperatures[st.top()], pop prev = st.top() and set ans[prev] = i - prev.
  4. Step 4: Push current index i onto st.
  5. Step 5: Any index remaining on stack at the end has no warmer day, naturally staying 0.
  6. Step 6: Return ans.

Daily Temperatures Forward Monotonic Stack Execution

2 of 2 questions left today
Step 1 / 8
Trace timeline13% explored
Current operationSTEP 1 OF 8
Stack holds unresolved day 0
Visual state
Values and pointers at this exact step
stack
TOP
idx 0 (73°)
Push adds to the top · Pop removes from the top
Why this step matters

Stack holds unresolved day 0.

Step 1 / 8
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4
5class Solution {
6public:
7 std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
8 int n = temperatures.size();
9 std::vector<int> ans(n, 0);
10 std::stack<int> st; // stores indices
11 for (int i = 0; i < n; i++) {
12 while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
13 int prev = st.top();
14 st.pop();
15 ans[prev] = i - prev;
16 }
17 st.push(i);
18 }
19 return ans;
20 }
21};
22
23int main() {
24 Solution solver;
25 std::vector<int> temps = {73, 74, 75, 71, 69, 72, 76, 73};
26 std::vector<int> ans = solver.dailyTemperatures(temps);
27 std::cout << "Output: [";
28 for (size_t i = 0; i < ans.size(); i++) {
29 std::cout << ans[i] << (i + 1 < ans.size() ? ", " : "");
30 }
31 std::cout << "]" << std::endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N) — Single forward pass where each index is pushed and popped at most once, giving O(N) linear time.
  • Space complexity: O(N) — O(N) worst-case space when temperatures are strictly decreasing.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force Nested SearchO(N^2)O(1)Scan forward from each day until a warmer temperature is found.Redundant comparisons on monotonically decreasing prefixes.
2.Right-to-Left Monotonic StackO(N)O(N)Maintain future candidates in decreasing order while scanning backwards.Memory allocation for stack.
3.Optimal Forward Monotonic StackOptimalO(N)O(N)Single forward pass; incoming warmer day resolves all smaller preceding pending indices.None (Optimal).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using >= instead of > for popping (temperatures must be strictly warmer).

Pitfall 2:

Storing values instead of indices and then being unable to calculate the distance.

Pitfall 3:

Forgetting that unresolved elements remaining on stack should have value 0 in output.

Crucial Edge Cases to Validate:

  • Strictly decreasing temperatures (e.g. `[90, 80, 70, 60]`) — No day has a warmer future day; returns all 0s [0, 0, 0, 0].
  • Strictly increasing temperatures (e.g. `[30, 40, 50, 60]`) — Every day is warmer the very next day; returns [1, 1, 1, 0].
  • All equal temperatures (e.g. `[70, 70, 70]`) — Strict inequality required; returns [0, 0, 0].
  • Single day `[50]` — Returns [0].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State clearly that this is a classic 'Next Greater Element' problem parameterized by index distance.
  2. Explain the monotonic invariant before writing code: 'The stack will always maintain indices with temperatures in non-increasing order'.
  3. Highlight why the runtime is O(N) amortized despite the nested while loop (each element pushed and popped at most once).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we store indices rather than temperature values in the stack?

2.What is the worst-case time complexity of the optimal monotonic stack?

Back to DSA Sheet