Monotonic Stack & LeetCode's "Daily Temperatures"

Let's dive into a cool data structure called the Monotonic Stack and see how it helps us solve a popular coding problem, "Daily Temperatures".

What's a Monotonic Stack?

Imagine a stack of books, but with a rule: you can only place a new book on top if it's lighter than the book already there. This creates a stack of books sorted by weight, from heaviest at the bottom to lightest at the top.

That's a monotonic stack. It's a regular stack, but it enforces a specific order on its elements – either always increasing or always decreasing.

Monotonically Increasing Stack: Elements are always in increasing order from bottom to top. [1, 2, 5, 8]
Monotonically Decreasing Stack: Elements are always in decreasing order from bottom to top. [10, 7, 4, 1]

This simple rule makes them incredibly efficient for problems where you need to find the "next greater element" or "previous smaller element" for items in a sequence.

The Problem: Daily Temperatures (LeetCode 739)

The problem is this: You're given a list of daily temperatures. For each day, you need to figure out how many days you have to wait for a warmer temperature. If no such day exists, the answer is 0.

Example:

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

Expected Output:

result = [1, 1, 4, 2, 1, 1, 0, 0]

Let's break down why:

For day 0 (73°), the next day (day 1) is warmer (74°). So, wait is 1 day.
For day 1 (74°), the next day (day 2) is warmer (75°). So, wait is 1 day.
For day 2 (75°), you have to wait until day 6 (76°). So, wait is 6 - 2 = 4 days.
...and so on.

The Solution: Using a Monotonically Decreasing Stack

We'll use a stack to store the indices of the days. We'll keep this stack monotonically decreasing, meaning the temperatures corresponding to the indices in the stack will always be going down.

Let's trace our example: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

Initialize result = [0, 0, 0, 0, 0, 0, 0, 0] and an empty stack.

Day 0: Temp = 73

Stack is empty. Push index 0.

Temperatures: [73, 74, 75, 71, 69, 72, 76, 73] ^ (Current: 73) Stack: | 0 | (Temp: 73) +---+

Day 1: Temp = 74

74 is warmer than temperatures[0] (73).
We found a warmer day for index 0!
Pop 0 from the stack.
result[0] = 1 (current index) - 0 (popped index) = 1.
Now the stack is empty. Push index 1.

Temperatures: [73, 74, 75, 71, 69, 72, 76, 73] ^ (Current: 74) Stack: | 1 | (Temp: 74) +---+ Result: [1, 0, 0, 0, 0, 0, 0, 0]

Day 2: Temp = 75

75 is warmer than temperatures[1] (74).
Pop 1. result[1] = 2 - 1 = 1.
Stack is empty. Push index 2.

Temperatures: [73, 74, 75, 71, 69, 72, 76, 73] ^ (Current: 75) Stack: | 2 | (Temp: 75) +---+ Result: [1, 1, 0, 0, 0, 0, 0, 0]

Day 3: Temp = 71

71 is not warmer than temperatures[2] (75).
The stack needs to stay decreasing. Push index 3.

Temperatures: [73, 74, 75, 71, 69, 72, 76, 73] ^ (Current: 71) Stack: | 3 | (Temp: 71) | 2 | (Temp: 75) +---+

Day 4: Temp = 69

69 is not warmer than temperatures[3] (71).
Push index 4.

Temperatures: [73, 74, 75, 71, 69, 72, 76, 73] ^ (Current: 69) Stack: | 4 | (Temp: 69) | 3 | (Temp: 71) | 2 | (Temp: 75) +---+

Day 5: Temp = 72

72 is warmer than temperatures[4] (69).
Pop 4. result[4] = 5 - 4 = 1.
72 is warmer than temperatures[3] (71).
Pop 3. result[3] = 5 - 3 = 2.
72 is NOT warmer than temperatures[2] (75). Stop popping.
Push index 5.

Temperatures: [73, 74, 75, 71, 69, 72, 76, 73] ^ (Current: 72) Stack: | 5 | (Temp: 72) | 2 | (Temp: 75) +---+ Result: [1, 1, 0, 2, 1, 0, 0, 0]

Day 6: Temp = 76

76 is warmer than temperatures[5] (72).
Pop 5. result[5] = 6 - 5 = 1.
76 is warmer than temperatures[2] (75).
Pop 2. result[2] = 6 - 2 = 4.
Stack is empty. Push index 6.

Temperatures: [73, 74, 75, 71, 69, 72, 76, 73] ^ (Current: 76) Stack: | 6 | (Temp: 76) +---+ Result: [1, 1, 4, 2, 1, 1, 0, 0]

Day 7: Temp = 73

73 is not warmer than temperatures[6] (76).
Push index 7.

Temperatures: [73, 74, 75, 71, 69, 72, 76, 73] ^ (Current: 73) Stack: | 7 | (Temp: 73) | 6 | (Temp: 76) +---+

End of Loop

The loop finishes. Any indices left in the stack (6 and 7) don't have a warmer day after them, so their results remain 0.

Final Result: [1, 1, 4, 2, 1, 1, 0, 0]

Code Example (JavaScript)

DATA_NODE: javascript

function dailyTemperatures(temperatures) { const result = new Array(temperatures.length).fill(0); const stack = []; // We'll store indices here for (let i = 0; i < temperatures.length; i++) { // While stack is not empty AND current temp is warmer than the temp at the index on top of the stack while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) { const prevIndex = stack.pop(); result[prevIndex] = i - prevIndex; } // Push the current index onto the stack stack.push(i); } return result; }

Code Example (GoLang)

DATA_NODE: go

func dailyTemperatures(temperatures []int) []int { n := len(temperatures) result := make([]int, n) stack := []int{} // We'll store indices here for i := 0; i < n; i++ { // While stack is not empty AND current temp is warmer than the temp at the index on top of the stack for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] { prevIndex := stack[len(stack)-1] stack = stack[:len(stack)-1] // Pop result[prevIndex] = i - prevIndex } // Push the current index onto the stack stack = append(stack, i) } return result }

And that's how a monotonic stack gives us an elegant and efficient solution!

Monotonic Stack with Daily Temperatures