Monotonic Stacks

1. Introduction: The Eliminator

You have a line of people facing forward. You want to know, for each person, who is the first person taller than them standing in front of them. If a 6-foot person is standing in front of a 5-foot person, the 5-foot person is completely blocked from view. For anyone standing behind them, the 5-foot person is entirely irrelevant. We can mathematically eliminate them!

This is the essence of a Monotonic Stack. "Monotonic" is a math term meaning strictly increasing or decreasing. A Monotonic Stack strictly maintains its elements in a sorted order. When a new element wants to enter the stack, it destroys (pops) any existing elements that violate the sorted order.

This specific destruction mechanic allows us to solve "Next Greater / Next Smaller" problems in $O(N)$ time, crushing the $O(N^2)$ brute force approach.

2. Core Concept: The Maintenance Loop

Every Monotonic Stack problem follows this exact template:

Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < arr.length; i++) {
    // THE MAINTENANCE LOOP
    // While the new element destroys the order, pop the weak elements!
    while (!stack.isEmpty() && arr[i] > stack.peek()) {
        int poppedElement = stack.pop();
        // The new element (arr[i]) is the "Next Greater Element" for the poppedElement!
        // Record the answer here!
    }
    // Now it's safe to add the new element
    stack.push(arr[i]);
}

The Golden Rule:

• If you want the Next Greater element, maintain a Decreasing Stack. (A large element kicks out smaller ones).
• If you want the Next Smaller element, maintain an Increasing Stack. (A small element kicks out larger ones).

3. Advanced Code Example: Daily Temperatures

Problem Statement: (LeetCode 739) 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.

The Insight: We want the "Next Greater Element", so we need a strictly Decreasing Stack. Crucially, the problem asks for the number of days to wait, which means we need the distance between the indices! Therefore, our stack must store Indices, not temperature values.

import java.util.ArrayDeque;
import java.util.Deque;

public class DailyTemperatures {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        
        // Stack stores INDICES
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            int currentTemp = temperatures[i];
            
            // While the current day is WARMER than the day at the top of the stack...
            while (!stack.isEmpty() && currentTemp > temperatures[stack.peek()]) {
                // The current day is the answer for the day we just popped!
                int previousDayIndex = stack.pop();
                
                // Calculate how many days we waited
                result[previousDayIndex] = i - previousDayIndex;
            }
            
            // Push the current day onto the stack to wait for a warmer day
            stack.push(i);
        }
        
        // Any indices left in the stack at the end naturally get 0 in the result array
        return result;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. Even with the while loop, every index is pushed onto the stack exactly once and popped at most once. Amortized time is strictly linear.
• Space Complexity: $O(N)$ for the Stack in the worst case (e.g., temperatures are continuously decreasing, [100, 90, 80], so nothing ever gets popped).

4. Advanced Code Example: Next Greater Element (Circular Array)

Problem Statement: (LeetCode 503) Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The Insight: Because it's a circular array, if we don't find a greater element to our right, we can wrap around and look to our left! How do we simulate wrapping around? We just run the exact same for loop twice! By iterating up to 2 * n - 1 and using modulo arithmetic i % n, we perfectly simulate a circular scan.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class NextGreaterCircular {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1); // Default to -1 if no greater element exists
        
        Deque<Integer> stack = new ArrayDeque<>();
        
        // Loop TWICE to simulate circular behavior
        for (int i = 0; i < 2 * n; i++) {
            int currentIndex = i % n; // Modulo keeps the index in bounds
            int currentNum = nums[currentIndex];
            
            while (!stack.isEmpty() && currentNum > nums[stack.peek()]) {
                int poppedIndex = stack.pop();
                result[poppedIndex] = currentNum;
            }
            
            // Only push elements onto the stack during the FIRST pass.
            // During the second pass, we only want to resolve pending elements in the stack!
            if (i < n) {
                stack.push(currentIndex);
            }
        }
        
        return result;
    }
}

5. Master Code Example: Largest Rectangle in Histogram

Problem Statement: (LeetCode 84) Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

This is the boss-fight of Monotonic Stacks. The Insight: A rectangle is bounded by the first bar to its left that is shorter, and the first bar to its right that is shorter. If we maintain an Increasing Stack, the moment we encounter a shorter bar, we trigger the while loop. The bar we pop is the bar we are evaluating. The current index is the right boundary (the shorter bar that triggered the pop). The new top of the stack is the left boundary (the shorter bar that was sitting safely underneath the popped bar). We can instantly calculate the area!

import java.util.ArrayDeque;
import java.util.Deque;

public class LargestRectangle {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        int n = heights.length;
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i <= n; i++) {
            // Trick: Use 0 height at the very end to force the stack to empty completely!
            int currentHeight = (i == n) ? 0 : heights[i];
            
            // We want an INCREASING stack. If we see a smaller bar, it's a boundary!
            while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {
                // The bar we are calculating the area for
                int targetHeight = heights[stack.pop()];
                
                // The width calculation:
                // Right boundary is the current index 'i'
                // Left boundary is whatever is left on the stack (or -1 if stack is empty)
                int leftBoundary = stack.isEmpty() ? -1 : stack.peek();
                int width = i - leftBoundary - 1;
                
                maxArea = Math.max(maxArea, targetHeight * width);
            }
            stack.push(i);
        }
        
        return maxArea;
    }
}

6. Common Mistakes Beginners Make

1. Storing Values instead of Indices

   • The Mistake: stack.push(temperatures[i])
   • Why it's wrong: You lose the spatial relationship. If you pop 80, how do you know if that 80 occurred on Day 2 or Day 5? You need the index to calculate distances and update result arrays correctly.

2. Confusing Increasing vs Decreasing

   • The Mistake: Using an Increasing Stack for Next Greater Element.
   • Why it's wrong: If you want Next Greater, you want small elements to be violently kicked out when a large element arrives (so you can record their answers). Therefore, the stack must normally sit in a Decreasing state until a disruptive large element forces the pops.

3. Processing the Answer at the Wrong Time

   • The Mistake: Trying to record answers when pushing to the stack.
   • Why it's wrong: When you push an element, you don't know its Next Greater Element yet! It hasn't happened. The answer is ONLY recorded for the element that gets popped.

7. Interview Q&A

Q1: What's the difference between Monotonic Stack and Monotonic Deque? Answer: Monotonic Stacks only mutate at one end (the top). They are used for finding the "Next Greater/Smaller" element. Monotonic Deques mutate at both ends. They are used for Sliding Window Minimum/Maximum problems because elements must eventually expire from the bottom of the queue based on time.

Q2: Can we find the "Previous Greater Element"? Answer: Yes! The exact same algorithm does this naturally. When you are processing arr[i], and the while loop finishes popping, whatever element is currently sitting at stack.peek() is the Previous Greater Element!

8. Practice Problems

1. Daily Temperatures (LeetCode 739)
   • Goal: Master the Decreasing Stack template.
2. Next Greater Element II (LeetCode 503)
   • Goal: Master the Circular array modulo trick.
3. Largest Rectangle in Histogram (LeetCode 84 - Hard)
   • Goal: Master the Increasing Stack and width calculation.

9. Summary

• The Use Case: Finding the Next/Previous Greater/Smaller element in strictly $O(N)$ time.
• The Core Loop: while(!stack.isEmpty() && current > stack.peek()) { pop(); resolve(); } push();.
• Indices over Values: Always store the array indices in the stack so you can calculate distances (current_index - popped_index).
• Decreasing Stack: Finds Next Greater.
• Increasing Stack: Finds Next Smaller.