Understanding Monotonic Stacks - A Powerful Pattern for Array Problems

Introduction

When solving array problems involving finding the next greater element, next smaller element, or their previous counterparts, a naive approach using nested loops results in O(n²) time complexity. Monotonic stacks provide an elegant solution that reduces this to O(n).

What is a Monotonic Stack?

A monotonic stack is a stack that maintains elements in either strictly increasing or strictly decreasing order. The key insight is that we can use this ordered structure to efficiently find relationships between elements.

Types of Monotonic Stacks

1. Monotonic Decreasing Stack: Elements decrease from bottom to top (smaller elements on top)

- Used to find the next greater element

2. Monotonic Increasing Stack: Elements increase from bottom to top (larger elements on top)

- Used to find the next smaller element

The Classic Problem: Next Greater Element

Given an array, find the next greater element for each element. If no greater element exists, return -1.

Example:

Input:  [4, 5, 2, 10, 8]
Output: [5, 10, 10, -1, -1]

Naive Approach (O(n²))

public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    
    for (int i = 0; i < n; i++) {
        result[i] = -1;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] > nums[i]) {
                result[i] = nums[j];
                break;
            }
        }
    }
    
    return result;
}

Monotonic Stack Approach (O(n))

The key idea: use a monotonic decreasing stack that stores indices. As we iterate, if the current element is greater than the element at the top of the stack, we've found the next greater element for that index.

import java.util.*;

public int[] nextGreaterElement(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++) {
        // While current element is greater than element at top index
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            int index = stack.pop();
            result[index] = nums[i]; // Found next greater element
        }
        stack.push(i); // Push current index
    }
    
    return result;
}

How It Works

Let's trace through the example [4, 5, 2, 10, 8]:

1. i = 0, nums[0] = 4

- Stack: []

- Push index 0: [0]

2. i = 1, nums[1] = 5

- Stack top: index 0, value 4

- 5 > 4 → Pop 0, set result[0] = 5

- Push index 1: [1]

3. i = 2, nums[2] = 2

- Stack top: index 1, value 5

- 2 < 5 → No pop, push index 2: [1, 2]

4. i = 3, nums[3] = 10

- Stack top: index 2, value 2

- 10 > 2 → Pop 2, set result[2] = 10

- Stack top: index 1, value 5

- 10 > 5 → Pop 1, set result[1] = 10

- Push index 3: [3]

5. i = 4, nums[4] = 8

- Stack top: index 3, value 10

- 8 < 10 → No pop, push index 4: [3, 4]

Final result: [5, 10, 10, -1, -1]

Why Monotonic Decreasing Stack Works

The stack maintains elements in decreasing order. When we encounter a larger element:

Common Variations

1. Next Smaller Element

Use a monotonic increasing stack:

public int[] nextSmallerElement(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++) {
        // While current element is smaller than element at top
        while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
            int index = stack.pop();
            result[index] = nums[i];
        }
        stack.push(i);
    }
    
    return result;
}

2. Previous Greater Element

Iterate from right to left with a decreasing stack:

public int[] previousGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Stack<Integer> stack = new Stack<>();
    
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            int index = stack.pop();
            result[index] = nums[i];
        }
        stack.push(i);
    }
    
    return result;
}

3. Previous Smaller Element

Iterate from right to left with an increasing stack:

public int[] previousSmallerElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Stack<Integer> stack = new Stack<>();
    
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
            int index = stack.pop();
            result[index] = nums[i];
        }
        stack.push(i);
    }
    
    return result;
}

Real-World Applications

Monotonic stacks are used in problems like:

1. Largest Rectangle in Histogram - Finding the largest rectangle that can be formed

2. Trapping Rain Water - Calculating trapped rainwater

3. Daily Temperatures - Finding days with warmer temperatures

4. Remove K Digits - Removing digits to form smallest number

5. Next Greater Node in Linked List - Finding next greater values

Time Complexity Analysis

Key Takeaways

1. Monotonic Decreasing Stack → Find next/previous greater element

2. Monotonic Increasing Stack → Find next/previous smaller element

3. Direction matters: Left-to-right finds "next", right-to-left finds "previous"

4. Stack stores indices (not values) for easy result array updates

5. Each element processed once → O(n) time complexity

Practice Problems

1. [Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/)

2. [Daily Temperatures](https://leetcode.com/problems/daily-temperatures/)

3. [Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)

4. [Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)

Conclusion

Monotonic stacks are a powerful pattern for solving array problems efficiently. By maintaining elements in sorted order, we can process relationships between elements in linear time. Master this pattern, and you'll find it applicable to many competitive programming and interview problems!