Monotonic Stack | Engineering Interview Kit

Concept

A Monotonic Stack is a specialized stack pattern used to solve exactly one specific type of problem: “Find the Next Greater (or Next Smaller) Element.”

The word monotonic means “strictly increasing” or “strictly decreasing”.
We enforce a rule on our stack: Before we push() a new item onto the stack, we must look at the top item. If pushing the new item would break the sorted order, we aggressively pop() the top item off until the stack is sorted again.

Daily Temperatures

The absolute best way to understand a Monotonic Stack is LeetCode #739: Daily Temperatures.
Problem: Given an array of daily temperatures, return an array answering: “How many days do you have to wait until a warmer temperature?”
Input: [73, 74, 75, 71, 69, 72, 76, 73]

The Naive Approach ( $O(N^2)$ ):
For day 1 (73), loop through the rest of the array until you find 74. For day 2 (74), loop through the rest until you find 75.

The Monotonic Stack Approach ( $O(N)$ ):
We use a Strictly Decreasing Stack. The stack will hold the indices of the days we are waiting to resolve.

Day 0 (73): Stack is empty. Push index 0. Stack: [0]
Day 1 (74): 74 is GREATER than 73.
- 74 is the answer that day 0 has been waiting for!
- We pop() day 0 off the stack. We calculate the difference in indices (1 - 0 = 1 day wait).
- We record 1 in our answer array.
- Stack is empty. Push index 1. Stack: [1]
Day 2 (75): 75 is GREATER than 74.
- We pop() day 1. Answer is 2 - 1 = 1.
- Push index 2. Stack: [2]
Day 3 (71): 71 is LESS than 75.
- It doesn’t break the decreasing order. Just push it!
- Stack: [2, 3] (Waiting for something warmer than 71 and 75).
Day 4 (69): 69 is LESS than 71. Push it!
- Stack: [2, 3, 4] (Temps: 75, 71, 69).
Day 5 (72): The Chain Reaction!
- 72 is GREATER than 69 (Day 4). Pop() Day 4. Answer: 5 - 4 = 1.
- Wait, 72 is ALSO GREATER than 71 (Day 3). Pop() Day 3. Answer: 5 - 3 = 2.
- 72 is LESS than 75 (Day 2). We stop popping.
- Push Day 5. Stack: [2, 5].

Implementation

// Time Complexity: O(N)
// Space Complexity: O(N)
function dailyTemperatures(temps: number[]): number[] {
    const answer = new Array(temps.length).fill(0);
    // Stack stores indices of the days we haven't found a warmer temp for yet
    const stack: number[] = []; 

    for (let currentDay = 0; currentDay < temps.length; currentDay++) {
        const currentTemp = temps[currentDay];
        
        // While the stack isn't empty AND the current temp is hotter than the top of the stack...
        while (stack.length > 0 && currentTemp > temps[stack[stack.length - 1]]) {
            // We found a warmer day! Pop the colder day off.
            const colderDay = stack.pop();
            
            // Calculate how many days we waited
            answer[colderDay] = currentDay - colderDay;
        }
        
        // Push the current day onto the stack to wait for a warmer day
        stack.push(currentDay);
    }

    return answer;
}

Why is it O(N)?

It looks like $O(N^2)$ because there is a while loop inside a for loop.
However, think about the physics of the stack: Every single index is pushed onto the stack exactly once. And it is popped off the stack at most exactly once.
Because an element cannot be popped twice, the while loop runs an absolute maximum of $N$ times across the entire execution of the program. Therefore, the total operations are $2N$ , which simplifies to strictly $O(N)$ .

Interview Questions

Q: You need to find the Next SMALLER element instead of the Next GREATER element. How do you change the algorithm?
A: You simply change the logic to maintain a Strictly Increasing Stack. The while loop condition changes from currentTemp > stack.top to currentTemp < stack.top. Whenever you encounter a smaller number, it triggers the chain reaction, popping off all the larger numbers that were waiting for it.

Q: How does the Monotonic Stack solve the famous “Trapping Rain Water” problem?
A: In Trapping Rain Water, a puddle can only form when there is a “dip” between two higher walls. You use a Strictly Decreasing Stack. You push heights onto the stack as long as they go down (forming the slope of the bowl). The moment you encounter a height that goes up, it breaks the monotonic rule! You found the right wall of the bowl. You pop() the bottom of the bowl off the stack, look at the new top of the stack (which is the left wall), and mathematically calculate width * height to find the exact volume of water trapped in that specific horizontal layer.