Monotonic Stack Complete Guide: Next Greater, Histogram, Rain Water & More

The monotonic stack is one of the most powerful patterns in DSA interviews. It looks simple but solves an entire family of “find the nearest larger/smaller element” problems in O(n). Once you internalise the pattern, you can apply it to a dozen LeetCode problems.

What is a Monotonic Stack?

A monotonic stack is a stack where elements are maintained in either strictly increasing or strictly decreasing order. When a new element arrives that would violate the order, we pop elements until the invariant is restored.

Key Insight: Amortised O(n)

Each element is pushed once and popped at most once. Even though we have nested loops, the total work across all iterations is O(n).

Two Flavours

Type	Elements in stack	What gets popped	Use case
Decreasing	Top is smallest	Smaller elements are popped by larger incoming	Next Greater Element
Increasing	Top is largest	Larger elements are popped by smaller incoming	Next Smaller Element

---

1. Next Greater Element

Problem: For each element, find the first element to its right that is greater. (LeetCode 496, 503)

The Algorithm

Use a monotonic decreasing stack (top is smallest). When a new element is larger than the top, the top has found its next greater element.

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices

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

    return result

Time: O(n) | Space: O(n)

Circular Array Variant (LeetCode 503)

Process the array twice (or use modular indexing):

def next_greater_circular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

    for i in range(2 * n):
        idx = i % n
        while stack and nums[idx] > nums[stack[-1]]:
            result[stack.pop()] = nums[idx]
        if i < n:
            stack.append(i)

    return result

---

2. Next Smaller Element

Same idea but use a monotonic increasing stack:

def next_smaller_element(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

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

    return result

Previous Greater / Previous Smaller

Scan from right to left instead:

def previous_smaller_element(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

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

    return result

---

3. Largest Rectangle in Histogram

Problem: Given an array of bar heights, find the area of the largest rectangle. (LeetCode 84)

The Insight

For each bar, the largest rectangle using that bar as the shortest bar extends left and right until a shorter bar is found. This is exactly “previous smaller” and “next smaller.”

def largest_rectangle_area(heights):
    n = len(heights)
    stack = []
    max_area = 0

    for i in range(n + 1):
        h = heights[i] if i < n else 0  # sentinel

        while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)

        stack.append(i)

    return max_area

Time: O(n) | Space: O(n)

Step-by-Step Walkthrough

For heights = [2, 1, 5, 6, 2, 3]:

i	h	Stack action	Area calculated
0	2	Push 0	-
1	1	Pop 0: height=2, width=1, area=2. Push 1	2
2	5	Push 2	-
3	6	Push 3	-
4	2	Pop 3: h=6, w=1, a=6. Pop 2: h=5, w=2, a=10. Push 4	10
5	3	Push 5	-
6	0	Pop 5: h=3, w=1, a=3. Pop 4: h=2, w=4, a=8. Pop 1: h=1, w=6, a=6	10

Answer: 10 (bars at index 2-3 with height 5).

Two-Pass Alternative

def largest_rectangle_two_pass(heights):
    n = len(heights)
    left = [0] * n   # index of previous smaller
    right = [0] * n   # index of next smaller

    # Previous smaller
    stack = []
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)

    # Next smaller
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)

    max_area = 0
    for i in range(n):
        max_area = max(max_area, heights[i] * (right[i] - left[i] - 1))

    return max_area

---

4. Maximal Rectangle in Binary Matrix

Problem: Given a binary matrix, find the largest rectangle containing only 1s. (LeetCode 85)

Reduction to Histogram

For each row, build a histogram of consecutive 1s in each column. Then apply “largest rectangle in histogram.”

def maximal_rectangle(matrix):
    if not matrix:
        return 0

    m, n = len(matrix), len(matrix[0])
    heights = [0] * n
    max_area = 0

    for i in range(m):
        for j in range(n):
            heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0

        max_area = max(max_area, largest_rectangle_area(heights))

    return max_area

Time: O(m * n) | Space: O(n)

---

5. Trapping Rain Water

Problem: Given elevation bars, compute how much rain water can be trapped. (LeetCode 42)

Approach 1: Monotonic Stack

Use a monotonic decreasing stack. When a taller bar arrives, water can be trapped between it and the previous taller bar.

def trap_stack(height):
    stack = []
    water = 0

    for i, h in enumerate(height):
        while stack and h > height[stack[-1]]:
            bottom = height[stack.pop()]
            if not stack:
                break
            width = i - stack[-1] - 1
            bounded_height = min(h, height[stack[-1]]) - bottom
            water += width * bounded_height

        stack.append(i)

    return water

Time: O(n) | Space: O(n)

Approach 2: Two Pointers (Optimal Space)

def trap_two_pointers(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1

    return water

Time: O(n) | Space: O(1)

Approach 3: Prefix Max Arrays

def trap_prefix(height):
    n = len(height)
    if n <= 2:
        return 0

    left_max = [0] * n
    right_max = [0] * n

    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])

    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])

    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]

    return water

Time: O(n) | Space: O(n)

---

6. Stock Span Problem

Problem: For each day, find how many consecutive previous days (including today) have a price less than or equal to today’s price. (LeetCode 901)

class StockSpanner:
    def __init__(self):
        self.stack = []  # (price, span)

    def next(self, price):
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

Time: O(1) amortised per call | Space: O(n)

---

7. Daily Temperatures

Problem: Given daily temperatures, for each day find how many days until a warmer temperature. Return 0 if no warmer day exists. (LeetCode 739)

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []  # indices

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

    return result

Time: O(n) | Space: O(n)

---

Choosing the Right Stack Type

I need to find…	Stack type	Pop condition
Next Greater Element	Decreasing	incoming > top
Next Smaller Element	Increasing	incoming < top
Previous Greater Element	Decreasing (scan L-R)	incoming >= top
Previous Smaller Element	Increasing (scan L-R)	incoming <= top

Template

def monotonic_stack_template(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

    for i in range(n):
        # For "next greater": while stack and nums[i] > nums[stack[-1]]
        # For "next smaller": while stack and nums[i] < nums[stack[-1]]
        while stack and CONDITION(nums[i], nums[stack[-1]]):
            idx = stack.pop()
            result[idx] = i  # or nums[i], depending on what you need
        stack.append(i)

    return result

---

Common Mistakes

1. Forgetting the sentinel. In histogram, appending a 0 at the end ensures all bars are processed.
2. Strict vs. non-strict comparison. For “next greater,” use >. For “next greater or equal,” use >=. This affects whether equal elements pop each other.
3. Storing values vs. indices. Always store indices. You can look up the value from the index, but not the other way around.
4. Trapping rain water: computing height wrong. The bounded height is min(left, right) - bottom, not min(left, right) - 0.
5. Off-by-one in width calculation. Width is i - stack[-1] - 1, not i - stack[-1].

---

Big-O Summary

Problem	Time	Space
Next Greater/Smaller	O(n)	O(n)
Largest Rectangle	O(n)	O(n)
Maximal Rectangle	O(m*n)	O(n)
Trapping Rain Water	O(n)	O(1) with two pointers
Stock Span	O(1) amortised	O(n)
Daily Temperatures	O(n)	O(n)

---

Practice Problems

Problem	Platform	Difficulty
Next Greater Element I	LeetCode 496	Easy
Next Greater Element II	LeetCode 503	Medium
Largest Rectangle in Histogram	LeetCode 84	Hard
Maximal Rectangle	LeetCode 85	Hard
Trapping Rain Water	LeetCode 42	Hard
Online Stock Span	LeetCode 901	Medium
Daily Temperatures	LeetCode 739	Medium
Sum of Subarray Minimums	LeetCode 907	Medium
132 Pattern	LeetCode 456	Medium
Remove K Digits	LeetCode 402	Medium