Monotonic Stack Pattern

📊 Monotonic Stack - Next Greater Element

Array:

Monotonic Stack (Decreasing):

Empty stack

Next Greater Element:

-1

Step 1: Start with 2: push to stack

Progress: 1 / 7

Speed:

Pattern:

Decreasing stack for next greater element: When we see a larger element, pop smaller ones from stack - the current element is their "next greater"! O(n) time.

🎯 Explain Like I'm 5...

Imagine kids standing in line 👧🧒👦 at different heights, looking for who's TALLER than them on their right! It's like finding your next taller neighbor!

📏 The Height Line: Kids with heights: 2, 1, 5, 6, 2, 3

• Kid at height 2: Look right → Who's first taller person? Height 5! ✅
• Kid at height 1: Look right → Height 5 is taller! ✅
• Kid at height 5: Look right → Height 6 is taller! ✅
• Kid at height 6: Look right → Nobody taller! 😢
• Kid at height 2: Look right → Height 3 is taller! ✅

Instead of looking at EVERYONE to the right (slow!), use a special helper stack! 📚

🚀 The Magic Stack: Keep a stack that's like a stairs going DOWN! 📉 When you see someone taller, they become the "next taller" for everyone shorter in the stack! Pop the shorter ones out! It's like clearing out the little kids when a tall kid shows up! 🎯

When Should You Use This Pattern?

✓Finding next greater/smaller element
✓Finding previous greater/smaller element
✓Histogram, stock span problems
✓Need O(n) solution for range queries

📝 Example 1: Next Greater Element

For each element, find the next greater element to its right.

Step-by-Step Thinking:

Use a decreasing monotonic stack
When we see a larger element, it's the "next greater" for stack elements
Pop smaller elements and record their answer
Push current element to stack

NextGreaterElement.java

java

import java.util.*;
public class NextGreaterElement {
    // Find next greater element for each element
    public static int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);  // Default: no greater element
        Stack<Integer> stack = new Stack<>();  // Store indices
        // Traverse array
        for (int i = 0; i < n; i++) {
            // Pop elements smaller than current
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                int idx = stack.pop();
                result[idx] = nums[i];  // Found next greater!
            }
            stack.push(i);  // Push current index
        }
        return result;
    }
    // Circular array version
    public static int[] nextGreaterCircular(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Stack<Integer> stack = new Stack<>();
        // Traverse twice for circular array
        for (int i = 0; i < 2 * n; i++) {
            int num = nums[i % n];
            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                result[stack.pop()] = num;
            }
            if (i < n) {
                stack.push(i);
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {2, 1, 5, 6, 2, 3};
        System.out.println("Next greater: " + Arrays.toString(nextGreaterElements(nums)));
        // Output: [5, 5, 6, -1, 3, -1]
        int[] circular = {1, 2, 1};
        System.out.println("Next greater (circular): " +
            Arrays.toString(nextGreaterCircular(circular)));
        // Output: [2, -1, 2]
    }
}

📝 Example 2: Largest Rectangle in Histogram

Find the largest rectangle area in a histogram.

LargestRectangle.java

java

import java.util.*;
public class LargestRectangle {
    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int n = heights.length;
        for (int i = 0; i < n; i++) {
            // Pop bars taller than current
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int height = heights[stack.pop()];
                // Width: from next smaller on left to current on right
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        // Process remaining bars
        while (!stack.isEmpty()) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? n : n - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        return maxArea;
    }
    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println("Largest rectangle: " + largestRectangleArea(heights));
        // Output: 10 (bars at index 2-3 with height 5, width 2)
        heights = new int[]{2, 4};
        System.out.println("Largest rectangle: " + largestRectangleArea(heights));
        // Output: 4
    }
}

📝 Example 3: Daily Temperatures

Find how many days you have to wait for a warmer temperature.

DailyTemperatures.java

java

import java.util.*;
public class DailyTemperatures {
    public static int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();  // Store indices
        for (int i = 0; i < n; i++) {
            // Found warmer day for days on stack
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int prevDay = stack.pop();
                result[prevDay] = i - prevDay;  // Days to wait
            }
            stack.push(i);
        }
        // Remaining days never get warmer (result already 0)
        return result;
    }
    // Stock Span Problem (similar concept)
    public static int[] stockSpan(int[] prices) {
        int n = prices.length;
        int[] span = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            // Pop days with smaller prices
            while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
                stack.pop();
            }
            // Span = current day - previous greater day
            span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
            stack.push(i);
        }
        return span;
    }
    public static void main(String[] args) {
        int[] temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
        System.out.println("Days to wait: " +
            Arrays.toString(dailyTemperatures(temperatures)));
        // Output: [1, 1, 4, 2, 1, 1, 0, 0]
        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        System.out.println("Stock span: " + Arrays.toString(stockSpan(prices)));
        // Output: [1, 1, 1, 2, 1, 4, 6]
    }
}

🔑 Key Points to Remember

1️⃣Increasing stack: find next/previous smaller
2️⃣Decreasing stack: find next/previous greater
3️⃣Time Complexity: O(n) - each element pushed/popped once!
4️⃣Store indices in stack (not values) for width calculations

💪 Practice Problems

• Trapping Rain Water
• Remove K Digits
• Maximum Width Ramp
• Sum of Subarray Minimums
• Online Stock Span