Monotonic Stack

A comprehensive guide for competitive programming and interviews.

What is a Monotonic Stack?
Intuition — Why Does It Work?
Visual Walkthrough
The Template — Next Greater Element
All Four Variants
Complexity Analysis
Classic Problems with Full Solutions
When to Use Monotonic Stack — Pattern Recognition
Common Mistakes

What is a Monotonic Stack?

A monotonic stack is a stack data structure where the elements are maintained in an increasing or decreasing order from bottom to top. Whenever we push a new element, we first pop all elements that would violate the monotonic invariant.

There are two types:

Monotonically Increasing Stack (bottom to top)

The stack maintains elements in non-decreasing order from bottom to top. When we encounter a new element, we pop all elements that are greater than the new element.

Bottom [1, 3, 5, 7] Top     ← increasing from bottom to top
       Push 4:
       Pop 7 (7 > 4)
       Pop 5 (5 > 4)
       Result: [1, 3, 4]    ← still increasing

Monotonically Decreasing Stack (bottom to top)

The stack maintains elements in non-increasing order from bottom to top. When we encounter a new element, we pop all elements that are smaller than the new element.

Bottom [7, 5, 3, 1] Top     ← decreasing from bottom to top
       Push 4:
       Pop 1 (1 < 4)
       Pop 3 (3 < 4)
       Result: [7, 5, 4]    ← still decreasing

Key Insight: When we pop an element from the stack, the element being pushed is the answer to some query about the popped element. For a decreasing stack, the pusher is the "next greater element" for everything it pops. For an increasing stack, the pusher is the "next smaller element."

Intuition — Why Does It Work?

The Core Problem

For each element in an array, find the next greater element to its right. That is, the first element to the right that is strictly larger.

Array:   [2, 1, 5, 6, 2, 3]
Answer:  [5, 5, 6,-1, 3,-1]
          ^  ^  ^      ^
          |  |  |      |
          |  |  |      3 is right of 2 and > 2
          |  |  6 is right of 5 and > 5
          |  5 is right of 1 and > 1
          5 is right of 2 and > 2

Brute Force: O(n^2)

For each element at index i, scan every element to its right until you find one that is larger. In the worst case (a sorted array), this is O(n^2).

CPP

// Brute force — O(n^2)
for (int i = 0; i < n; i++) {
    result[i] = -1;
    for (int j = i + 1; j < n; j++) {
        if (arr[j] > arr[i]) {
            result[i] = arr[j];
            break;
        }
    }
}

Why Monotonic Stack is O(n)

The key observation: each element is pushed onto the stack exactly once and popped at most once. That means across the entire algorithm, there are at most 2n stack operations, giving us O(n) total time.

Why does this work? Think of it like a line of people standing in a queue, where each person can only see the first person in front of them who is taller:

Heights:  2  1  5  6  2  3

Person 2 (height 2): "I can see person 5 (height 5) — they're the first taller one"
Person 1 (height 1): "I can also see person 5 (height 5)"
Person 5 (height 5): "I can see person 6 (height 6)"
Person 6 (height 6): "I can't see anyone taller — answer is -1"
Person 2 (height 2): "I can see person 3 (height 3)"
Person 3 (height 3): "Nobody taller to my right — answer is -1"

The insight is: once person 5 appears, persons 2 and 1 no longer matter for anyone to the right of 5. If some future person is looking for the next greater element, person 5 will always block persons 2 and 1 from being relevant. So we can safely discard (pop) 2 and 1 from consideration.

This is exactly what the monotonic stack does — it maintains a set of "candidates" that could still be the answer for some future element. When a larger element arrives, it eliminates all smaller candidates.

The Amortized Argument

Total push operations: exactly n (every element pushed once)
Total pop operations:  at most n (every element popped at most once)
─────────────────────────────────────────────────────────
Total operations:      at most 2n = O(n)

Even though a single step might pop many elements (imagine pushing a very large element that pops everything), the total pops across ALL steps cannot exceed n.

Visual Walkthrough

Let's trace through the "Next Greater Element to the Right" algorithm on:

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

We maintain a stack of indices (storing indices lets us record results and is more flexible). The stack will be decreasing in terms of the values at those indices.

═══════════════════════════════════════════════════════════════════
Step 1: i=0, arr[0]=2
   Stack is empty, just push.
   Stack (bottom→top): [0]       values: [2]
   Result: [-1, -1, -1, -1, -1, -1]

═══════════════════════════════════════════════════════════════════
Step 2: i=1, arr[1]=1
   arr[1]=1 < arr[stack.top()]=arr[0]=2   →  don't pop, just push
   Stack (bottom→top): [0, 1]    values: [2, 1]
   Result: [-1, -1, -1, -1, -1, -1]

   Visualization of stack:
        |   |
        | 1 |  ← top (index 1, value 1)
        | 2 |       (index 0, value 2)
        └───┘

═══════════════════════════════════════════════════════════════════
Step 3: i=2, arr[2]=5
   arr[2]=5 > arr[stack.top()]=arr[1]=1   →  POP index 1
       next greater of arr[1]=1 is arr[2]=5    →  result[1] = 5
   arr[2]=5 > arr[stack.top()]=arr[0]=2   →  POP index 0
       next greater of arr[0]=2 is arr[2]=5    →  result[0] = 5
   Stack is empty, push index 2.
   Stack (bottom→top): [2]       values: [5]
   Result: [5, 5, -1, -1, -1, -1]

   What happened visually:
        |   |         |   |         |   |
        | 1 |  5 >1   |   |  5 >2   |   |
        | 2 |  ───→   | 2 |  ───→   | 5 |  ← push 5
        └───┘         └───┘         └───┘

═══════════════════════════════════════════════════════════════════
Step 4: i=3, arr[3]=6
   arr[3]=6 > arr[stack.top()]=arr[2]=5   →  POP index 2
       next greater of arr[2]=5 is arr[3]=6    →  result[2] = 6
   Stack is empty, push index 3.
   Stack (bottom→top): [3]       values: [6]
   Result: [5, 5, 6, -1, -1, -1]

═══════════════════════════════════════════════════════════════════
Step 5: i=4, arr[4]=2
   arr[4]=2 < arr[stack.top()]=arr[3]=6   →  don't pop, just push
   Stack (bottom→top): [3, 4]    values: [6, 2]
   Result: [5, 5, 6, -1, -1, -1]

   Stack visualization:
        |   |
        | 2 |  ← top (index 4, value 2)
        | 6 |       (index 3, value 6)
        └───┘

═══════════════════════════════════════════════════════════════════
Step 6: i=5, arr[5]=3
   arr[5]=3 > arr[stack.top()]=arr[4]=2   →  POP index 4
       next greater of arr[4]=2 is arr[5]=3    →  result[4] = 3
   arr[5]=3 < arr[stack.top()]=arr[3]=6   →  don't pop
   Push index 5.
   Stack (bottom→top): [3, 5]    values: [6, 3]
   Result: [5, 5, 6, -1, 3, -1]

═══════════════════════════════════════════════════════════════════
End of array — remaining elements in stack have no next greater element.
   Index 3 (value 6): result[3] = -1  (already -1)
   Index 5 (value 3): result[5] = -1  (already -1)

FINAL RESULT: [5, 5, 6, -1, 3, -1]
═══════════════════════════════════════════════════════════════════

The Template — Next Greater Element

CPP

#include <bits/stdc++.h>
using namespace std;

// Next Greater Element to the RIGHT
// For each element, find the first element to its right that is strictly greater.
// Returns the VALUE of the next greater element, or -1 if none exists.
vector<int> nextGreaterRight(vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1);
    stack<int> st; // stores INDICES (not values!)

    // Traverse left to right
    for (int i = 0; i < n; i++) {
        // Pop elements whose "next greater" is arr[i]
        while (!st.empty() && arr[st.top()] < arr[i]) {
            result[st.top()] = arr[i]; // arr[i] is the next greater for arr[st.top()]
            st.pop();
        }
        st.push(i);
    }
    // Elements remaining in stack have no next greater element → result stays -1
    return result;
}

int main() {
    vector<int> arr = {2, 1, 5, 6, 2, 3};
    vector<int> res = nextGreaterRight(arr);

    cout << "Array:  ";
    for (int x : arr) cout << x << " ";
    cout << "\nResult: ";
    for (int x : res) cout << x << " ";
    cout << "\n";
    // Output:
    // Array:  2 1 5 6 2 3
    // Result: 5 5 6 -1 3 -1
}

Why We Store Indices, Not Values

Storing indices instead of values gives us two critical advantages:

We can write to the result array. When we pop index j, we set result[j] = arr[i]. If we stored values, we wouldn't know which position to write to.
We can compute distances. Many problems (like Daily Temperatures) need the distance i - j between an element and its next greater. With indices, this is trivial.

All Four Variants

There are four natural "next element" queries. Each is solved by a monotonic stack with a specific iteration direction and comparison.

Cheat Sheet

Rule of thumb:

Greater queries → pop elements smaller than current (maintain decreasing stack)
Smaller queries → pop elements larger than current (maintain increasing stack)
Right queries → iterate left to right (the current element is the answer for popped elements)
Left queries → iterate right to left (the current element is the answer for popped elements)

Variant 1: Next Greater to the RIGHT

Already shown above. Iterate left to right. When arr[i] pops arr[j], it means arr[i] is the next greater element to the right of arr[j].

CPP

vector<int> nextGreaterRight(vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1);
    stack<int> st;

    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[st.top()] < arr[i]) {
            result[st.top()] = arr[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}
// Array:  [4, 5, 2, 10, 8]
// Result: [5, 10, 10, -1, -1]

Variant 2: Next Greater to the LEFT

Iterate right to left. When arr[i] pops arr[j], it means arr[i] is the next greater element to the left of arr[j] (since i < j when we iterate right to left, i is to the left of j).

CPP

vector<int> nextGreaterLeft(vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1);
    stack<int> st;

    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && arr[st.top()] < arr[i]) {
            result[st.top()] = arr[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}
// Array:  [4, 5, 2, 10, 8]
// Result: [-1, -1, 5, -1, 10]

Alternative approach (often simpler for "left" queries): Iterate left to right and read the answer from the stack directly. The element just below the current in the stack is the nearest greater to the left.

CPP

vector<int> nextGreaterLeft_v2(vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1);
    stack<int> st;

    for (int i = 0; i < n; i++) {
        // Pop elements smaller than or equal to current — they can't be
        // "next greater to the left" for anyone at index >= i
        while (!st.empty() && arr[st.top()] <= arr[i]) {
            st.pop();
        }
        // The top of the stack (if any) is the nearest greater element to the left
        if (!st.empty()) {
            result[i] = arr[st.top()];
        }
        st.push(i);
    }
    return result;
}
// Array:  [4, 5, 2, 10, 8]
// Result: [-1, -1, 5, -1, 10]

Variant 3: Next Smaller to the RIGHT

Iterate left to right, pop elements larger than current. Maintain an increasing stack.

CPP

vector<int> nextSmallerRight(vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1);
    stack<int> st;

    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[st.top()] > arr[i]) {
            result[st.top()] = arr[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}
// Array:  [4, 5, 2, 10, 8]
// Result: [2, 2, -1, 8, -1]

Variant 4: Next Smaller to the LEFT

Iterate right to left, pop elements larger than current. Maintain an increasing stack.

CPP

vector<int> nextSmallerLeft(vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1);
    stack<int> st;

    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && arr[st.top()] > arr[i]) {
            result[st.top()] = arr[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}
// Array:  [4, 5, 2, 10, 8]
// Result: [-1, 4, -1, 2, 2]

Alternative (iterate left to right, read from stack):

CPP

vector<int> nextSmallerLeft_v2(vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1);
    stack<int> st;

    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[st.top()] >= arr[i]) {
            st.pop();
        }
        if (!st.empty()) {
            result[i] = arr[st.top()];
        }
        st.push(i);
    }
    return result;
}
// Array:  [4, 5, 2, 10, 8]
// Result: [-1, 4, -1, 2, 2]

Complexity Analysis

Time Complexity: O(n)

The crucial insight is that the inner while loop does not make this O(n^2). We need to analyze the total work across all iterations of the outer loop.

Claim: Each element is pushed exactly once and popped at most once.

Proof:
  - The outer for-loop pushes each element exactly once.           → n pushes total
  - An element can only be popped once (once it's popped, it's gone). → at most n pops total
  - Total stack operations: at most 2n = O(n).

Therefore, the amortized cost per element is O(1), and the total time is O(n).

This is an example of amortized analysis — even though a single iteration of the for loop might pop O(n) elements, the total work across ALL iterations is bounded by O(n).

Space Complexity: O(n)

The stack can hold at most n elements (when the array is sorted in the order matching the stack's monotonic property).
The result array takes O(n) space.

Classic Problems with Full Solutions

Problem 1: Largest Rectangle in Histogram (LeetCode 84)

Problem: Given an array heights where heights[i] is the height of a bar in a histogram (each bar has width 1), find the area of the largest rectangle that can be formed within the histogram.

Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10

Histogram visualization:

        ┌───┐
        │   │
    ┌───┤   │
    │   │   │         ┌───┐
 ┌──┤   │   ├───┐     │   │
 │  │   │   │   ├─────┤   │
 │  │   │   │   │     │   │
─┴──┴───┴───┴───┴─────┴───┴──
  2   1   5   6   2     3

The largest rectangle (area = 10) is formed by bars at indices 2 and 3:

        ┌───┐
        │███│
    ┌───┤███│
    │███│███│
    │███│███│
 ┌──┤███│███├───┐     ┌───┐
 │  │███│███│   ├─────┤   │
 │  │███│███│   │     │   │
─┴──┴───┴───┴───┴─────┴───┴──
  2   1   5   6   2     3

  Width = 2, Height = 5, Area = 10

Key Insight: For each bar of height h, the largest rectangle using that bar as the shortest bar extends as far left and as far right as possible until we hit a bar shorter than h. So the width is:

width = (index of next smaller to the right) - (index of next smaller to the left) - 1

This is precisely two monotonic stack queries!

The Elegant One-Pass Solution:

Instead of computing "next smaller left" and "next smaller right" separately, we can do it in a single pass using a stack that maintains increasing order of heights.

When we encounter a bar shorter than the top of the stack, we pop. The popped bar's rectangle is bounded on the right by the current index i and on the left by the new top of the stack (after popping). This gives us both boundaries at once.

Why width = i - st.top() - 1  (after popping):

  Consider the moment we pop index `j` because heights[i] < heights[j]:

  Stack (before pop): [..., a, j]     where heights[a] < heights[j]
                                      (a is the new top after popping j)

  Bar at index j can extend:
    - Left boundary:  a + 1  (can't go past bar at index a, which is shorter)
    - Right boundary: i - 1  (can't go past bar at index i, which is shorter)
    - Width: (i - 1) - (a + 1) + 1 = i - a - 1 = i - st.top() - 1

  Special case: if the stack is empty after popping, the bar extends all the way
  to the left edge → width = i.

  Diagram:
    heights:   ...  a  ...  j  ...  i  ...
    values:        low      high    low
                    ↑                ↑
                    left boundary    right boundary
                    (exclusive)      (exclusive)

    Width = i - a - 1

Complete C++ Solution:

CPP

#include <bits/stdc++.h>
using namespace std;

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    stack<int> st;
    int maxArea = 0;

    // Process each bar plus one extra "virtual bar" of height 0 at the end.
    // The virtual bar ensures everything gets popped from the stack.
    for (int i = 0; i <= n; i++) {
        // Current height: use 0 for the virtual bar at position n
        int curHeight = (i == n) ? 0 : heights[i];

        while (!st.empty() && heights[st.top()] > curHeight) {
            // Pop the bar — it is the shortest bar in the rectangle we're computing
            int height = heights[st.top()];
            st.pop();

            // Width: from (st.top() + 1) to (i - 1), inclusive
            // If stack is empty, bar extends from index 0 to i-1, so width = i
            int width = st.empty() ? i : (i - st.top() - 1);

            maxArea = max(maxArea, height * width);
        }
        st.push(i);
    }
    return maxArea;
}

int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << largestRectangleArea(heights) << "\n"; // Output: 10
}

Step-by-step trace:

heights = [2, 1, 5, 6, 2, 3], virtual bar at index 6 with height 0

i=0, h=2: push 0.                     Stack: [0]
i=1, h=1: pop 0 (height 2).
          width = 1 (stack empty → i=1). area = 2*1 = 2.
          push 1.                      Stack: [1]
i=2, h=5: push 2.                     Stack: [1, 2]
i=3, h=6: push 3.                     Stack: [1, 2, 3]
i=4, h=2: pop 3 (height 6).
          width = 4 - 2 - 1 = 1.      area = 6*1 = 6.
          pop 2 (height 5).
          width = 4 - 1 - 1 = 2.      area = 5*2 = 10.  ← MAXIMUM
          push 4.                      Stack: [1, 4]
i=5, h=3: push 5.                     Stack: [1, 4, 5]
i=6, h=0: pop 5 (height 3).
          width = 6 - 4 - 1 = 1.      area = 3*1 = 3.
          pop 4 (height 2).
          width = 6 - 1 - 1 = 4.      area = 2*4 = 8.
          pop 1 (height 1).
          width = 6 (stack empty).     area = 1*6 = 6.

Answer: maxArea = 10

Complexity: Time O(n), Space O(n).

Problem 2: Daily Temperatures (LeetCode 739)

Problem: Given an array temperatures, return an array answer where answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day with a warmer temperature, answer[i] = 0.

Input:  [73, 74, 75, 71, 69, 72, 76, 73]
Output: [ 1,  1,  4,  2,  1,  1,  0,  0]

Intuition: This is literally "Next Greater Element to the Right" but instead of returning the value, we return the distance (number of days).

Day 0 (73°): Next warmer is Day 1 (74°) → wait 1 day
Day 1 (74°): Next warmer is Day 2 (75°) → wait 1 day
Day 2 (75°): Next warmer is Day 6 (76°) → wait 4 days
Day 3 (71°): Next warmer is Day 5 (72°) → wait 2 days
Day 4 (69°): Next warmer is Day 5 (72°) → wait 1 day
Day 5 (72°): Next warmer is Day 6 (76°) → wait 1 day
Day 6 (76°): No warmer day              → wait 0 days
Day 7 (73°): No warmer day              → wait 0 days

Complete C++ Solution:

CPP

#include <bits/stdc++.h>
using namespace std;

vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> answer(n, 0);
    stack<int> st; // stores indices

    for (int i = 0; i < n; i++) {
        // Pop days that found their next warmer day
        while (!st.empty() && temperatures[st.top()] < temperatures[i]) {
            int prevDay = st.top();
            st.pop();
            answer[prevDay] = i - prevDay; // distance in days
        }
        st.push(i);
    }
    // Remaining indices in stack → no warmer day → answer stays 0
    return answer;
}

int main() {
    vector<int> temps = {73, 74, 75, 71, 69, 72, 76, 73};
    vector<int> ans = dailyTemperatures(temps);
    for (int x : ans) cout << x << " ";
    // Output: 1 1 4 2 1 1 0 0
}

Complexity: Time O(n), Space O(n).

Problem 3: Stock Span Problem (LeetCode 901)

Problem: The stock span for a given day is the maximum number of consecutive days (starting from that day and going backwards) for which the stock price was less than or equal to the price on the given day.

Prices: [100, 80, 60, 70, 60, 75, 85]
Spans:  [  1,  1,  1,  2,  1,  4,  6]

Day 0 (100): No previous day ≤ 100 before it stops    → span 1
Day 1 ( 80): 80 > nothing (100 blocks)                → span 1
Day 2 ( 60): 60 > nothing (80 blocks)                 → span 1
Day 3 ( 70): 70 ≥ 60 → span extends left 1 extra day  → span 2
Day 4 ( 60): 60 > nothing (70 blocks)                 → span 1
Day 5 ( 75): 75 ≥ 60, 75 ≥ 70, 75 ≥ 60               → span 4
Day 6 ( 85): 85 ≥ 75, 85 ≥ 60, 85 ≥ 70, 85 ≥ 60, 85 ≥ 80  → span 6

Intuition: The span is i - index_of_previous_greater_element. This is exactly the "Next Greater to the Left" variant! We need the index of the nearest element to the left that is strictly greater than the current price.

Prices:               [100, 80, 60, 70, 60, 75, 85]
Prev Greater (index): [ -1, 0,  1,  1,  3,  1,  0]
Span = i - prev:      [  1, 1,  1,  2,  1,  4,  6]

Complete C++ Solution:

CPP

#include <bits/stdc++.h>
using namespace std;

class StockSpanner {
    stack<pair<int, int>> st; // (price, index)
    int idx;
public:
    StockSpanner() : idx(0) {}

    int next(int price) {
        // Pop all prices ≤ current price (they're not "previous greater")
        while (!st.empty() && st.top().first <= price) {
            st.pop();
        }
        // Span = distance to previous greater element
        int span = st.empty() ? (idx + 1) : (idx - st.top().second);
        st.push({price, idx});
        idx++;
        return span;
    }
};

// Batch version for an array:
vector<int> stockSpan(vector<int>& prices) {
    int n = prices.size();
    vector<int> span(n);
    stack<int> st; // stores indices

    for (int i = 0; i < n; i++) {
        // Pop indices with prices ≤ current
        while (!st.empty() && prices[st.top()] <= prices[i]) {
            st.pop();
        }
        // If stack empty, all previous prices were ≤ current → span = i + 1
        span[i] = st.empty() ? (i + 1) : (i - st.top());
        st.push(i);
    }
    return span;
}

int main() {
    vector<int> prices = {100, 80, 60, 70, 60, 75, 85};
    vector<int> spans = stockSpan(prices);
    for (int s : spans) cout << s << " ";
    // Output: 1 1 1 2 1 4 6
}

Complexity: Time O(n), Space O(n).

Problem 4: Trapping Rain Water (LeetCode 42)

Problem: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6

Elevation map with trapped water (shown as ~):

              ┌──┐
       ┌──┐~~│  │
       │  ├──┤  ├──┐  ┌──┐
 ┌──┐~~│  │  │  │  ├──┤  ├──┐
─┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──
  0  1  0  2  1  0  1  3  2  1  2  1

Water trapped:
  Index 2:  min(1,2) - 0 = 1
  Index 4:  min(2,3) - 1 = 1
  Index 5:  min(2,3) - 0 = 2
  Index 6:  min(2,3) - 1 = 1
  Index 9:  min(3,2) - 1 = 1
  Total = 6

The Monotonic Stack Approach:

While the two-pointer approach is more common for this problem, the monotonic stack approach gives a different perspective: we compute water layer by layer horizontally rather than column by column vertically.

Intuition: We maintain a decreasing stack. When we find a bar taller than the top, it means water can be trapped between the current bar and the bar below the top of the stack, with the top of the stack being the "bottom" of the water.

When we pop index `top` because heights[i] > heights[top]:

  Stack: [..., left, top]   and current bar is at index i

  heights[left] > heights[top]  (stack is decreasing)
  heights[i]    > heights[top]  (that's why we're popping)

  Water is trapped between bars `left` and `i`, above bar `top`:

  heights[left]                    heights[i]
       ┌──┐                           ┌──┐
       │  │ ~~~~~~~~water~~~~~~~~ │  │
       │  │    heights[top]        │  │
       │  ├────────┤    ├──────────┤  │
       │  │        │    │          │  │
  ─────┴──┴────────┴────┴──────────┴──┴─────
       left       top              i

  bounded_height = min(heights[left], heights[i]) - heights[top]
  width          = i - left - 1
  water         += bounded_height * width

Complete C++ Solution:

CPP

#include <bits/stdc++.h>
using namespace std;

int trap(vector<int>& height) {
    int n = height.size();
    stack<int> st; // stores indices, maintaining decreasing heights
    int water = 0;

    for (int i = 0; i < n; i++) {
        // While current bar is taller than the top of the stack,
        // water can be trapped
        while (!st.empty() && height[st.top()] < height[i]) {
            int bottom = st.top(); // the "floor" of the water
            st.pop();

            if (st.empty()) break; // no left boundary

            int left = st.top(); // left boundary (taller bar to the left)

            int bounded_height = min(height[left], height[i]) - height[bottom];
            int width = i - left - 1;

            water += bounded_height * width;
        }
        st.push(i);
    }
    return water;
}

int main() {
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    cout << trap(height) << "\n"; // Output: 6
}

Detailed Trace:

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

i=0, h=0: push 0.          Stack: [0]
i=1, h=1: pop 0 (h=0).     Stack empty → no left wall → break.
          push 1.           Stack: [1]
i=2, h=0: push 2.          Stack: [1, 2]
i=3, h=2: pop 2 (h=0).     left=1 (h=1). bounded_h = min(1,2)-0 = 1. w = 3-1-1 = 1.
                            water += 1.  (Total: 1)
          pop 1 (h=1).      Stack empty → break.
          push 3.           Stack: [3]
i=4, h=1: push 4.          Stack: [3, 4]
i=5, h=0: push 5.          Stack: [3, 4, 5]
i=6, h=1: pop 5 (h=0).     left=4 (h=1). bounded_h = min(1,1)-0 = 1. w = 6-4-1 = 1.
                            water += 1.  (Total: 2)
          h[4]=1 not < h[6]=1 → stop.
          push 6.           Stack: [3, 4, 6]
i=7, h=3: pop 6 (h=1).     left=4 (h=1). bounded_h = min(1,3)-1 = 0. w = 7-4-1 = 2.
                            water += 0.  (Total: 2)
          pop 4 (h=1).      left=3 (h=2). bounded_h = min(2,3)-1 = 1. w = 7-3-1 = 3.
                            water += 3.  (Total: 5)
          pop 3 (h=2).      Stack empty → break.
          push 7.           Stack: [7]
i=8, h=2: push 8.          Stack: [7, 8]
i=9, h=1: push 9.          Stack: [7, 8, 9]
i=10,h=2: pop 9 (h=1).     left=8 (h=2). bounded_h = min(2,2)-1 = 1. w = 10-8-1 = 1.
                            water += 1.  (Total: 6)
          h[8]=2 not < h[10]=2 → stop.
          push 10.          Stack: [7, 8, 10]
i=11,h=1: push 11.         Stack: [7, 8, 10, 11]

Answer: water = 6

Complexity: Time O(n), Space O(n).

Problem 5: Maximal Rectangle (LeetCode 85) — Bonus

Problem: Given a binary matrix filled with 0s and 1s, find the largest rectangle containing only 1s and return its area.

Key Insight: Reduce to "Largest Rectangle in Histogram" by treating each row as the base of a histogram. For each cell, compute the height = number of consecutive 1s above (including itself). Then apply the histogram algorithm to each row.

Matrix:          Heights row by row:
1 0 1 0 0       1 0 1 0 0   → max rect in [1,0,1,0,0] = 1
1 0 1 1 1       2 0 2 1 1   → max rect in [2,0,2,1,1] = 3
1 1 1 1 1       3 1 3 2 2   → max rect in [3,1,3,2,2] = 6
1 0 0 1 0       4 0 0 3 0   → max rect in [4,0,0,3,0] = 4

Answer: 6 (from row 2: the 3x2 rectangle spanning columns 2-4)

CPP

#include <bits/stdc++.h>
using namespace std;

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    stack<int> st;
    int maxArea = 0;
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!st.empty() && heights[st.top()] > h) {
            int height = heights[st.top()]; st.pop();
            int width = st.empty() ? i : (i - st.top() - 1);
            maxArea = max(maxArea, height * width);
        }
        st.push(i);
    }
    return maxArea;
}

int maximalRectangle(vector<vector<char>>& matrix) {
    if (matrix.empty()) return 0;
    int rows = matrix.size(), cols = matrix[0].size();
    vector<int> heights(cols, 0);
    int maxArea = 0;

    for (int r = 0; r < rows; r++) {
        // Update histogram heights
        for (int c = 0; c < cols; c++) {
            heights[c] = (matrix[r][c] == '1') ? heights[c] + 1 : 0;
        }
        maxArea = max(maxArea, largestRectangleArea(heights));
    }
    return maxArea;
}

Complexity: Time O(rows * cols), Space O(cols).

When to Use Monotonic Stack — Pattern Recognition

Strong Signals (almost certainly monotonic stack)

"Next greater/smaller element" — The textbook application.
"Previous greater/smaller element" — Same technique, different direction.
"How far can this bar/element extend left/right?" — Histogram-type problems.
Stock span, daily temperatures — How many consecutive elements satisfy a condition.

Moderate Signals (consider monotonic stack)

"Find the largest rectangle/area" — Usually histogram reduction + monotonic stack.
"Remove digits/characters to make the result smallest/largest" — Greedy + monotonic stack (e.g., LC 402: Remove K Digits).
"Find the nearest element with some property" — Nearest greater, nearest smaller.

The Key Question to Ask Yourself

"For each element, do I need information about the nearest element to its left or right that is larger or smaller?"

If yes, use a monotonic stack.

Problem Categories

Common Mistakes

1. Confusing Indices vs Values

Wrong:

CPP

stack<int> st;
st.push(arr[i]);  // Pushing VALUE
// Later: result[st.top()] = arr[i];  // BUG: st.top() is a value, not an index!

Right:

CPP

stack<int> st;
st.push(i);  // Push INDEX
// Later: result[st.top()] = arr[i];  // Correct: st.top() is an index

2. Forgetting to Handle Remaining Elements

After processing all elements, anything left in the stack has no next greater/smaller element. Make sure the result array is initialized to -1 (or whatever the default is).

CPP

vector<int> result(n, -1); // Initialize to -1 — handles remaining elements automatically

3. Off-by-One in Width Calculations (Histogram)

The width formula i - st.top() - 1 requires careful reasoning:

i is the right boundary (exclusive)
st.top() is the left boundary (exclusive)
Width = number of bars between them = i - st.top() - 1

When the stack is empty, the bar extends all the way to the left edge → width = i.

4. Using `<=` vs `<` Incorrectly

For strictly greater: use < (pop elements strictly less than current). For greater or equal: use <= (pop elements less than or equal to current).

Be careful with duplicates! If the array has duplicate values, the choice between < and <= affects whether equal elements are treated as "greater" or not. For problems like "Sum of Subarray Minimums" (LC 907), this distinction is critical to avoid double-counting.

5. Wrong Iteration Direction

Next ___ to the RIGHT → iterate LEFT to RIGHT
Next ___ to the LEFT  → iterate RIGHT to LEFT (or read from stack while going left to right)

If you iterate in the wrong direction, you'll get "previous" instead of "next" (or vice versa).