DSA sheet · Stack · Monotonic stack pattern

Daily Temperatures

This is the third monotonic stack problem. Under a story about weather, it's the next greater element to the right again. The twist: we must answer "how many days later", not "which temperature". That forces one important change: the stack stores indices, not values. The teacher also shows that the same problem can be solved walking left to right, and explains exactly what changes when you do that.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Stacks, monotonic stacks and the 4 standard problems
• Part A · Brute force: two loops
• Part B · Optimal: stack of indices, walking from the right
• Part C · The same stack walking from the left
• Part D · Revision page

Part 0 · Before starting

Stack basics

A stack is a pile you can only use from the top: LIFO (Last In, First Out). Python's list works as a stack:

Drawings on this page: left = bottom, right = top.

Monotonic stack in one paragraph

A monotonic stack keeps its items in sorted order from bottom to top. Before pushing a new item, we pop every item on top that would break the order. For "next greater" questions we pop the items that are not greater than the new one. A popped item is hidden behind a closer item that is at least as big, so it can never be the "first bigger one" for anything that comes later. Every item is pushed once and popped at most once, which is why the whole thing is O(n).

The 4 standard problems (the teacher lists them here)

If you know stacks, you know these four. Almost every monotonic-stack question is one of them in disguise:

Translating this question: "warmer" means greater. "Days you have to wait" means the future, so to the right. (If the question asked about a warmer day in the past, it would be next greater to the left.) So Daily Temperatures = next greater to the right, but report the distance.

Part A · Brute force: two loops

LeetCode 739

1The question in simple words

You get the temperature for each day. For every day i, return how many days you must wait until a strictly warmer day. If no warmer day ever comes, return 0 for that day.

• Day 0 (73): the very next day is 74, warmer → wait 1.
• Day 1 (74): next day 75 → 1.
• Day 2 (75): 71, 69, 72 are all colder. Day 6 (76) is the first warmer day → wait 6 − 2 = 4.
• Day 6 (76): no warmer day after it → 0. Day 7 (73): it's the last day → 0.

Key observation: the wait is just the difference of indices, j − i, where j is the first warmer day after i.

2What the constraints tell us

• Length from 1 to 10⁵. Temperatures between 30 and 100.
• The teacher's reason for reading constraints: they tell you in advance whether the brute force will pass. Brute force here is O(n²) = 10⁵ × 10⁵ = 10¹⁰ steps. Past ~10⁸ it's unsafe, and from 10⁹ it's a sure TLE.
• So we write the brute force to understand the problem, then optimise to O(n).
• Length ≥ 1, so the input is never empty (our code still handles an empty list).

3Intuition

Stand on day i. Walk forward day by day until it's warmer. Count the steps. That count is the answer.

4Building the logic

And once a warmer day is found, break. We want the first one, so going further would only risk overwriting it with a later, wrong day.

5Approach steps

1. ans = [0] * n.
2. For i from 0 to n−2, for j from i+1 to n−1:
3. If temps[j] > temps[i]: ans[i] = j − i, break.
4. Return ans.

6Code (Python)

class Solution:
    def dailyTemperatures(self, temperatures):
        n = len(temperatures)
        ans = [0] * n                                # 0 = no warmer day
        for i in range(n - 1):
            for j in range(i + 1, n):                # only future days
                if temperatures[j] > temperatures[i]: # strictly warmer
                    ans[i] = j - i                   # days waited = index gap
                    break                            # first warmer day only
        return ans

7Code line by line

8Dry run (the interesting row, i = 2)

The other rows find their warmer day in one or two steps. Final [1, 1, 4, 2, 1, 1, 0, 0] ✓.

9Complexity & remember

• Time O(n²). The worst case is temperatures that never rise (e.g. 100, 99, 98, …): every inner loop scans to the end. At n = 10⁵ that's ~10¹⁰ → TLE (it does TLE when submitted).
• Space O(1) extra.

Part B · Optimal: stack of indices, walking from the right

1The question again

Same question. Target: O(n), with one loop and a stack.

2What the constraints tell us

n ≤ 10⁵ → O(n) is about 2·10⁵ stack operations, which is instant. O(n) extra space for the stack is allowed.

3Intuition

Since the answer lives in the future (to the right), walk from the last day backwards, exactly like Next Greater Element. When we're at day i, every later day has already been seen and summarised in the stack: the stack holds the days that could still be "the next warmer day" for someone, with the nearest on top.

The one new idea: in Next Greater Element we pushed values. Here we need how far away the warmer day is, so we push the index of the day. From an index we can get both things we need:

• its temperature: temperatures[st[-1]], used for comparing;
• its distance: st[-1] - i, used for the answer.

4Building the logic from the example (as the teacher walks it)

• Day 7 (73): the stack is empty, so no future day → 0. Push index 7.
• Day 6 (76): top is day 7 (73). Is 73 warmer than 76? No → pop it. The stack is empty → 0. Push 6.
• Day 5 (72): top is day 6 (76), warmer → answer 6 − 5 = 1. We don't search deeper: the top is the nearest candidate. Push 5.
• Day 4 (69): top is day 5 (72), warmer → 5 − 4 = 1. Push 4.
• Day 3 (71): top is day 4 (69), colder → pop. Why is it safe to throw 69 away? Every day to the left of day 3 sees 71 before it sees 69, and 71 is hotter. So if 69 were warm enough for that day, 71 is too, and it comes first. 69 can never again be anyone's "next warmer day". Next top is day 5 (72), warmer → 5 − 3 = 2. Push 3.
• Day 2 (75): top day 3 (71), colder → pop. Top day 5 (72), colder → pop (same reason: 75 now stands in front of both). Top day 6 (76), warmer → 6 − 2 = 4. Push 2.
• Day 1 (74): top day 2 (75) → 1. Push 1.
• Day 0 (73): top day 1 (74) → 1. Push 0.

5Approach steps

1. ans = [0] * n, empty stack (of indices).
2. For i from n−1 down to 0, with t = temperatures[i]:
3. While the stack is not empty and temperatures[top] ≤ t → pop.
4. If the stack is not empty → ans[i] = top − i.
5. Push i.
6. Return ans.

6Code (Python)

class Solution:
    def dailyTemperatures(self, temperatures):
        n = len(temperatures)
        ans = [0] * n
        st = []                                          # indices of future days, nearest on top
        for i in range(n - 1, -1, -1):
            t = temperatures[i]
            while st and temperatures[st[-1]] <= t:     # not warmer -> shadowed forever
                st.pop()
            if st:
                ans[i] = st[-1] - i                      # distance to the next warmer day
            st.append(i)                                 # push the INDEX, not the value
        return ans

7Code line by line

8Dry run: [73, 74, 75, 71, 69, 72, 76, 73]

Stack entries are written as index(temp) to make reading easy. The real stack holds only the index.

9Complexity & remember

• Time O(n): the for loop runs n times. Across the whole run, the stack sees n pushes and at most n pops. Even in the worst case, where one hot day pops everything, each index is popped only once. Total ≈ 2n = O(n).
• Space O(n) for the stack (e.g. temperatures rising every day keep every index on the stack when walking from the right).

Part C · The same stack walking from the left

1The question

The teacher answers a natural doubt: "Must we start from the right? Can't we go from the left?" We can. The code is almost the same, but where we write the answer changes.

2What the constraints tell us

Nothing new: still O(n) time and O(n) space, so both directions pass.

3Intuition: the stack becomes a waiting room

Walking from the left, when we stand on day i we don't know the future yet. So we can't answer day i right now. Instead we flip the roles:

• The stack holds the days that are still waiting for a warmer day. Think of a waiting room.
• Today (day i) might be the warmer day that some of those waiting days are looking for. If today is warmer than the top waiting day, today is that day's answer. Pop it and write ans[top] = i − top.
• Keep popping while today is warmer than the top. Then today joins the waiting room.

4Building the logic from the example

• Day 0 (73): no one is waiting. Push 0.
• Day 1 (74): 74 > 73, so day 0 is answered: ans[0] = 1 − 0 = 1. Pop it, push 1.
• Day 2 (75): answers day 1 → 1. Push 2.
• Day 3 (71) and day 4 (69): colder than the top, so they just join the waiting room. Stack: 2(75), 3(71), 4(69).
• Day 5 (72): warmer than 69 → ans[4] = 1. Warmer than 71 → ans[3] = 5 − 3 = 2. Not warmer than 75 → stop. Push 5.
• Day 6 (76): answers day 5 (1) and day 2 (6 − 2 = 4). Push 6.
• Day 7 (73): colder than 76 → push. Days 6 and 7 stay waiting forever → their answer stays 0.

5Approach steps

1. ans = [0] * n, empty stack.
2. For i from 0 to n−1, with t = temperatures[i]:
3. While the stack is not empty and t > temperatures[top]: pop j, set ans[j] = i − j.
4. Push i.
5. Return ans (whatever is still waiting keeps 0).

6Code (Python)

class Solution:
    def dailyTemperatures(self, temperatures):
        n = len(temperatures)
        ans = [0] * n
        st = []                                          # indices of days still waiting
        for i in range(n):
            t = temperatures[i]
            while st and t > temperatures[st[-1]]:      # today is warmer than the top waiter
                j = st.pop()
                ans[j] = i - j                           # answer goes to the POPPED day
            st.append(i)                                 # today starts waiting
        return ans

7Code line by line

8Dry run

9Complexity & remember

• Time O(n): each index is pushed once and popped at most once.
• Space O(n): e.g. falling temperatures keep every day waiting.

Part D · Revision page

s = Solution()
print(s.dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))  # [1, 1, 4, 2, 1, 1, 0, 0]
print(s.dailyTemperatures([30, 40, 50, 60]))                  # [1, 1, 1, 0]
print(s.dailyTemperatures([30, 60, 90]))                      # [1, 1, 0]
print(s.dailyTemperatures([70, 70, 70]))                      # [0, 0, 0]
print(s.dailyTemperatures([50]))                              # [0]

Based on this video: Daily Temperatures | Monotonic Stack