Monotonic Stack Pattern¶

Overview¶

Stack that maintains elements in strictly increasing or decreasing order. Enables O(n) solutions for "next greater/smaller element" problems and range queries.

When to Use¶

Next greater/smaller element
Previous greater/smaller element
Stock span problems
Histogram area problems
Temperature/wait time problems
Expression evaluation

Monotonic Stack Visualization

Template Code¶

Next Greater Element¶

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Stack<Integer> stack = new Stack<>();  // Stores indices

    for (int i = 0; i < n; i++) {
        // Pop elements smaller than current
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }

    return result;
}

Next Greater Element II (Circular Array)¶

public int[] nextGreaterElementsCircular(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Stack<Integer> stack = new Stack<>();

    // Process array twice for circular
    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;
}

Previous Smaller Element¶

public int[] previousSmaller(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < n; i++) {
        // Pop elements >= current
        while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
            stack.pop();
        }

        if (!stack.isEmpty()) {
            result[i] = nums[stack.peek()];
        }

        stack.push(i);
    }

    return result;
}

Daily Temperatures¶

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Stack<Integer> stack = new Stack<>();  // Indices

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
            int prevDay = stack.pop();
            result[prevDay] = i - prevDay;
        }
        stack.push(i);
    }

    return result;
}

Stock Span Problem¶

// How many consecutive days before had price <= today
public int[] stockSpan(int[] prices) {
    int n = prices.length;
    int[] span = new int[n];
    Stack<Integer> stack = new Stack<>();  // Indices

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
            stack.pop();
        }

        span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
        stack.push(i);
    }

    return span;
}

Largest Rectangle in Histogram¶

public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int maxArea = 0;
    int n = heights.length;

    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];

        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }

        stack.push(i);
    }

    return maxArea;
}

Maximal Rectangle in Binary Matrix¶

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) return 0;

    int m = matrix.length, n = matrix[0].length;
    int[] heights = new int[n];
    int maxArea = 0;

    for (int i = 0; i < m; i++) {
        // Update heights for current row
        for (int j = 0; j < n; j++) {
            heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
        }

        maxArea = Math.max(maxArea, largestRectangleArea(heights));
    }

    return maxArea;
}

Trapping Rain Water (Monotonic Stack)¶

public int trap(int[] height) {
    Stack<Integer> stack = new Stack<>();
    int water = 0;

    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int bottom = stack.pop();

            if (stack.isEmpty()) break;

            int left = stack.peek();
            int width = i - left - 1;
            int h = Math.min(height[i], height[left]) - height[bottom];
            water += width * h;
        }

        stack.push(i);
    }

    return water;
}

Remove K Digits¶

public String removeKdigits(String num, int k) {
    if (k >= num.length()) return "0";

    Stack<Character> stack = new Stack<>();

    for (char c : num.toCharArray()) {
        while (k > 0 && !stack.isEmpty() && stack.peek() > c) {
            stack.pop();
            k--;
        }
        stack.push(c);
    }

    // Remove remaining from end
    while (k > 0) {
        stack.pop();
        k--;
    }

    // Build result
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
    }
    sb.reverse();

    // Remove leading zeros
    while (sb.length() > 1 && sb.charAt(0) == '0') {
        sb.deleteCharAt(0);
    }

    return sb.toString();
}

Sum of Subarray Minimums¶

public int sumSubarrayMins(int[] arr) {
    int MOD = 1_000_000_007;
    int n = arr.length;
    long result = 0;

    // For each element, count subarrays where it's minimum
    int[] left = new int[n];   // Distance to previous smaller
    int[] right = new int[n];  // Distance to next smaller

    Stack<Integer> stack = new Stack<>();

    // Previous smaller element
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
            stack.pop();
        }
        left[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
        stack.push(i);
    }

    stack.clear();

    // Next smaller element
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
            stack.pop();
        }
        right[i] = stack.isEmpty() ? n - i : stack.peek() - i;
        stack.push(i);
    }

    // Calculate contribution of each element
    for (int i = 0; i < n; i++) {
        result = (result + (long) arr[i] * left[i] * right[i]) % MOD;
    }

    return (int) result;
}

Online Stock Span (Class Design)¶

class StockSpanner {
    Stack<int[]> stack;  // [price, span]

    public StockSpanner() {
        stack = new Stack<>();
    }

    public int next(int price) {
        int span = 1;

        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }

        stack.push(new int[]{price, span});
        return span;
    }
}

Time & Space Complexity¶

Problem	Time	Space
Next greater element	O(n)	O(n)
Daily temperatures	O(n)	O(n)
Stock span	O(n)	O(n)
Histogram area	O(n)	O(n)
Trapping rain water	O(n)	O(n)
Remove K digits	O(n)	O(n)

Common Interview Questions¶

Next Greater Element I, II - Basic monotonic stack
Daily Temperatures - Days until warmer
Stock Span Problem - Consecutive days <= price
Largest Rectangle in Histogram - Max rectangle area
Maximal Rectangle - Max rectangle of 1s in matrix
Trapping Rain Water - Water trapped between bars
Remove K Digits - Smallest number after removal
Sum of Subarray Minimums - Sum of mins of all subarrays
132 Pattern - Find i < j < k with nums[i] < nums[k] < nums[j]
Remove Duplicate Letters - Smallest lexicographic order
Online Stock Span - Class design
Asteroid Collision - Simulate collisions

Tips & Tricks¶

Store indices in stack, not values (access values via array)
Increasing stack: find next/previous smaller
Decreasing stack: find next/previous greater
For circular arrays, process 2n elements with modulo
Histogram pattern: calculate area when popping
Add sentinel (0) at end to force remaining elements to pop
For "contribution" problems, count subarrays where element is min/max