Monotonic Stack Explained: Next Greater Element & Largest Rectangle

A Monotonic Stack is one of the most important coding interview patterns because it transforms many seemingly quadratic $O(N^2)$ problems into efficient $O(N)$ solutions.

If you are preparing for coding interviews, the monotonic stack is a coding interview pattern you cannot afford to ignore. If you try to solve "next greater element" or "largest rectangle" problems with nested loops, you will likely hit a Time Limit Exceeded (TLE) error on LeetCode.

The secret to solving these problems in $O(N)$ time is a specialized data structure pattern called the Monotonic Stack.

What is a Monotonic Stack?

A standard stack follows Last-In-First-Out (LIFO) mechanics. A Monotonic Stack is simply a stack where the elements inside are always strictly increasing or strictly decreasing.

• Monotonic Decreasing Stack: Elements inside are sorted in descending order (largest at the bottom, smallest at the top).
• Monotonic Increasing Stack: Elements inside are sorted in ascending order (smallest at the bottom, largest at the top).

The "Aha!" Moment: Why is it Monotonic?

The magic happens when we try to push a new element onto the stack. Before pushing, we pop all elements from the stack that violate the monotonic property.

Let's trace an incoming array [5, 3, 7, 6] using a Decreasing Stack:

Incoming 5: Push 5. Stack: [5]
Incoming 3: 3 < 5. Push 3. Stack: [5, 3]
Incoming 7: 7 > 3. Pop 3! 7 > 5. Pop 5! Push 7. Stack: [7]
Incoming 6: 6 < 7. Push 6. Stack: [7, 6]

Because every element is pushed exactly once and popped exactly once, the overall time complexity is strictly $O(N)$, even with the while loop inside! This is called amortized analysis, one of the most common interview concepts.

Handling Duplicates (< vs <=)

The choice between strictly monotonic and non-strictly monotonic depends on the problem. * Using < (e.g., while stack and nums[i] < nums[stack[-1]]) keeps duplicates in the stack. * Using <= (e.g., while stack and nums[i] <= nums[stack[-1]]) removes duplicates. Many interview questions (like "Sum of Subarray Minimums") depend heavily on this subtle difference to avoid double-counting.

The Generic Template

Almost all monotonic stack problems can be reduced to this generic template:

stack = []

for i in range(len(nums)):
    # Changing the comparison changes the stack type
    # '<' -> Decreasing Stack (finds Next Greater)
    # '>' -> Increasing Stack (finds Next Smaller)
    while stack and condition(nums[i], nums[stack[-1]]):
        # Process the popped element
        popped = stack.pop()

    stack.append(i)

Why store indices instead of values?

In 90% of interview problems, you should store indices, not values. Indices let you: 1. Calculate distances and widths (crucial for histogram problems). 2. Map results back to the original array. 3. Access original values easily via nums[stack[-1]].

Pattern 1: Next Greater Element (Decreasing Stack)

The Problem: Given an array, for every element, find the first element to its right that is strictly greater than it. If none exists, return -1.

Example: [2, 1, 2, 4, 3] Output: [4, 2, 4, -1, -1]

The Intuition

We use a Monotonic Decreasing Stack that stores indices. We iterate through the array. If the current element is greater than the element at the top of the stack, we have found the "Next Greater Element" for the stack's top element! We pop it, record the answer, and keep checking the next top.

flowchart TD
    A[Iterate Array] --> B{Current > Stack Top?}
    B -->|Yes| C[Pop Stack Top]
    C --> D[Record Current as NGE for Popped Index]
    D --> B
    B -->|No| E[Push Current Index to Stack]
    E --> A

    style C fill:#4CAF50,color:#fff
    style E fill:#2196F3,color:#fff

Visualizing the Stack Evolution

Let's trace [2, 1, 2, 4, 3]:

The Code

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # Stores indices, maintains decreasing values

    for i in range(n):
        while stack and nums[i] > nums[stack[-1]]:
            prev_index = stack.pop()
            result[prev_index] = nums[i]

        stack.append(i)

    return result

print(next_greater_element([2, 1, 2, 4, 3])) 
# Output: [4, 2, 4, -1, -1]

Pattern 2: Largest Rectangle in Histogram (Increasing Stack)

The Problem: You are given an array of integers heights representing a histogram's bar heights. The width of each bar is 1. Return the area of the largest rectangle that can be formed.

Example: [2, 1, 5, 6, 2, 3] → Output: 10

Visualizing the Histogram

Index: 0 1 2 3 4 5
Array: [2, 1, 5, 6, 2, 3]

           █  █
           █  █
           █  █
     █     █  █     █
     █  █  █  █  █  █
     █  █  █  █  █  █

The Intuition

To find the largest rectangle, for every bar, we need to know: How far to the left and right can this bar extend? It can extend until it hits a bar shorter than itself.

This means we need to find the Previous Smaller Element (PSE) and the Next Smaller Element (NSE) for every bar.

We use a Monotonic Increasing Stack. When we encounter a bar shorter than the stack's top, we have found the NSE for the top bar! Furthermore, the element just below the popped bar on the stack is its PSE.

💡 The Dummy Element Trick: To avoid dealing with edge cases, we append a 0 to the end of the heights array. This forces the stack to empty itself at the end of the loop, ensuring every bar gets processed.

The Code

def largest_rectangle_area(heights):
    # Append 0 to force the stack to empty at the end
    heights = heights + [0]
    max_area = 0
    stack = []  # Stores indices, maintains increasing heights

    for i, h in enumerate(heights):
        while stack and h < heights[stack[-1]]:
            # The popped bar is the one we are calculating the area for
            height = heights[stack.pop()]

            # If stack is empty, width extends from 0 to i
            # Otherwise, width is from (previous smaller index + 1) to i
            width = i if not stack else i - stack[-1] - 1

            area = height * width
            max_area = max(max_area, area)

        stack.append(i)

    return max_area

print(largest_rectangle_area([2, 1, 5, 6, 2, 3])) # Output: 10

Understanding the Output: Looking at the histogram above, the maximum rectangle is formed by bars at index 2 and 3 (heights 5 and 6). The rectangle is limited by the shorter bar, giving it a height of 5 and a width of 2, which results in an area of $5 \times 2 = 10$.

Complexity Analysis

Why is it $O(N)$ if there is a while loop inside a for loop? This is a classic amortized analysis question. Every element is pushed onto the stack exactly once, and popped from the stack exactly once. Across the entire execution, the while loop will run at most $N$ times total, making the overall time complexity strictly $O(N)$.

💼 Interview Tip

When you see phrases like next greater, previous smaller, nearest warmer day, or largest rectangle, stop and ask yourself whether a monotonic stack applies. These are classic signals that it may lead to an optimal $O(N)$ solution. This pattern is often combined with Sliding Window, Prefix Sum, and Binary Search on Answer.

Decision Tree: When to Use What

flowchart TD
    A[Need next/previous element?] --> B{Greater or Smaller?}
    B -->|Greater| C{Next or Previous?}
    C -->|Next| D[Decreasing Stack]
    C -->|Previous| E[Decreasing Stack]
    B -->|Smaller| F{Next or Previous?}
    F -->|Next| G[Increasing Stack]
    F -->|Previous| H[Increasing Stack]

Pattern Recognition Table

In an interview, look for these signals in the problem statement, grouped from basic to advanced:

Common Mistakes to Avoid

1. Using values instead of indices: Always store indices. You need them to calculate widths and distances.
2. Using < instead of <=: Be careful with duplicates. If the problem says "strictly greater," your comparison operator must match that logic.
3. Forgetting the dummy element: In problems like Largest Rectangle, forgetting to append a 0 (or iterate one extra time) means the stack won't fully empty, and you'll miss the rectangles that extend to the end of the array.
4. Using the wrong stack type: If you need the Next Smaller, you must use an Increasing stack. It's counter-intuitive at first, but the incoming smaller element is what triggers the pop.

Comparison: Stack vs. Queue vs. Heap

Readers often confuse these structures.

Real-World Uses

"When do I actually use this?" Outside of LeetCode, monotonic stacks are highly practical: * Stock Price Analysis: Finding the span of days where a stock price was lower than today. * Weather Forecasting: Finding the nearest future day with a higher temperature. * Histogram/Image Processing: Finding largest rectangular regions (e.g., character segmentation in OCR). * Skyline or Terrain Analysis: Calculating visible buildings or water trapping between elevations. * Memory Allocation / Interval Processing: Finding contiguous free memory blocks or merging intervals.

Real Interview Questions & Practice Problems

Frequently Asked Questions (FAQ)

Should I store indices or values in the stack? In 90% of problems, you should store indices, not values. Storing indices allows you to calculate widths (like in Largest Rectangle) and map results back to the original array positions.

Monotonic Stack vs. Monotonic Queue? A Monotonic Stack is used for problems where you process elements in one pass and only care about elements to the right (or left). A Monotonic Queue (which allows popping from the front) is used in Sliding Window problems where you need to maintain the max/min of a moving window of fixed size $K$.

How do I handle circular arrays (like Next Greater Element II)? To handle a circular array, simply iterate through the array twice (loop from 0 to 2N - 1) and use modulo arithmetic (i % N) to access the elements. This simulates the circular nature without duplicating the array in memory.