Om's Brain

5. Monotonic Stack

18 min read

1️⃣ Core Idea

Pop elements that can no longer contribute to any future answer.

Why Monotonic Stack?

Brute force for “next greater element” = O(n²). Monotonic stack = O(n). Every element is pushed once and popped at most once → 2n operations total.

2️⃣ When to Think Monotonic Stack 🚀

✔️ Strong Signals

  • “Next greater element”
  • “Previous smaller element”
  • “Largest rectangle in histogram”
  • “Trapping rain water”
  • “Stock span” / “Daily temperatures”
  • “Sum of subarray minimums/maximums”
  • “Remove k digits” to make smallest number
  • Any problem asking about the nearest larger/smaller element in either direction

✔️ Hidden Signals

  • Finding boundaries (left boundary, right boundary) for each element
  • “How far can element i extend left/right?”
  • DP where A[i] = min(A[j:k]) + C → monotonic deque variant
  • “132 pattern” — relationships between three elements

3️⃣ The Four Monotonic Stack Types

TypePropertyExample
Strictly IncreasingEach element > previous[1, 4, 5, 8, 9]
Non-decreasingEach element >= previous[1, 4, 5, 5, 8]
Strictly DecreasingEach element < previous[9, 8, 5, 4, 1]
Non-increasingEach element <= previous[9, 9, 8, 5, 5]

4️⃣ The Four Templates (Master These!)

Convention

  • Stack always stores indices (st.top() is an index, arr[st.top()] is the value)
  • Default value: -1 for “no previous element”, n for “no next element”
  • Previous → traverse Left → Right (building answer as we go)
  • Next → traverse Right → Left (building answer as we go)

The Inverse Rule

Greater elements → use a Decreasing stack (pop smaller ones) Smaller elements → use an Increasing stack (pop larger ones) Think of it as opposites attract.

Template 1 — Next Greater Element (NGE)

// Next Greater Element (strictly greater)
// Stack type: Strictly Decreasing (pop when <= current)
// Traversal: Right → Left | Condition: <=
vector<int> nge(n);
stack<int> st;
 
for (int i = n - 1; i >= 0; i--) {
    while (!st.empty() && arr[st.top()] <= arr[i])
        st.pop();
 
    nge[i] = st.empty() ? n : st.top();
 
    st.push(i);
}

Template 2 — Next Smaller Element (NSE)

// Next Smaller Element (strictly smaller)
// Stack type: Strictly Increasing (pop when >= current)
// Traversal: Right → Left | Condition: >=
vector<int> nse(n);
stack<int> st;
 
for (int i = n - 1; i >= 0; i--) {
    while (!st.empty() && arr[st.top()] >= arr[i])
        st.pop();
 
    nse[i] = st.empty() ? n : st.top();
 
    st.push(i);
}

What’s happening? Going right to left, we pop everything >= current → what remains is strictly smaller → that’s our NSE.

Template 3 — Previous Smaller Element (PSE)

// Previous Smaller Element (strictly smaller)
// Stack type: Strictly Increasing (pop when >= current)
// Traversal: Left → Right | Condition: >=
vector<int> pse(n);
stack<int> st;
 
for (int i = 0; i < n; i++) {
    while (!st.empty() && arr[st.top()] >= arr[i])
        st.pop();
 
    pse[i] = st.empty() ? -1 : st.top();
 
    st.push(i);
}

What’s happening? We pop everything >= current → what remains on top is strictly smaller → that’s our PSE.

Template 4 — Previous Greater Element (PGE)

// Previous Greater Element (strictly greater)
// Stack type: Strictly Decreasing (pop when <= current)
// Traversal: Left → Right | Condition: <=
vector<int> pge(n);
stack<int> st;
 
for (int i = 0; i < n; i++) {
    while (!st.empty() && arr[st.top()] <= arr[i])
        st.pop();
 
    pge[i] = st.empty() ? -1 : st.top();
 
    st.push(i);
}

📋 Complete Cheatsheet

TemplateWhatTraversalConditionDefaultStack Type
PSEPrev SmallerLeft → Right>=-1Strictly Increasing
NSENext SmallerRight → Left>=nStrictly Increasing
PGEPrev GreaterLeft → Right<=-1Strictly Decreasing
NGENext GreaterRight → Left<=nStrictly Decreasing

🔀 Handling Duplicates — Strict vs Non-Strict

Sometimes you need “next greater or equal” instead of “next strictly greater”. Just flip the operator:

What you wantCondition in while loop
Strictly smaller>=
Smaller or equal>
Strictly greater<=
Greater or equal<

Duplicate Handling in Problems like "Sum of Subarray Mins"

When duplicates exist, use one strict and one non-strict boundary to avoid double counting. Example: PSE uses >= (strict) and NSE uses > (non-strict), or vice versa.

🔄 Single-Pass Merged Template (PSE + NSE Together) ( IGNORE THIS POINT )

You can compute both Previous Smaller and Next Smaller in a single left-to-right pass:

// Single-pass: PSE (strictly smaller) + NSE (smaller or equal)
// Note: one is strict, the other is non-strict — handles duplicates
vector<int> pse(n, -1), nse(n, n);
stack<int> st;
 
for (int i = 0; i < n; i++) {
    while (!st.empty() && arr[st.top()] >= arr[i]) {
        nse[st.top()] = i;     // current element is NSE for popped element
        st.pop();
    }
 
    pse[i] = st.empty() ? -1 : st.top();  // stack top is PSE for current
 
    st.push(i);
}

Strict vs Non-Strict in Merged Template

With >=: PSE is strictly smaller, but NSE becomes smaller or equal (not strict). With >: PSE is smaller or equal, but NSE becomes strictly smaller. Pick based on what the problem needs. For most problems (like histogram), either works as long as you’re consistent.

Similarly for PGE + NGE merged:

// Single-pass: PGE (strictly greater) + NGE (greater or equal)
vector<int> pge(n, -1), nge(n, n);
stack<int> st;
 
for (int i = 0; i < n; i++) {
    while (!st.empty() && arr[st.top()] <= arr[i]) {
        nge[st.top()] = i;
        st.pop();
    }
 
    pge[i] = st.empty() ? -1 : st.top();
 
    st.push(i);
}

5️⃣ Pattern 1 — Direct NGE / NSE Problems

These problems directly ask for the next/previous greater/smaller element.

Next Greater Element I — LC 496 ⭐

Given two arrays nums1 (subset of nums2), find the next greater element for each element of nums1 in nums2.

// LC 496. Next Greater Element I
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    int n = nums2.size();
    unordered_map<int, int> nge;
    stack<int> st;
 
    // NGE template on nums2 (Right → Left)
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && st.top() <= nums2[i])
            st.pop();
 
        nge[nums2[i]] = st.empty() ? -1 : st.top();
 
        st.push(nums2[i]);  // push values since we need a map
    }
 
    vector<int> res;
    for (int& x : nums1)
        res.push_back(nge[x]);
 
    return res;
}
// TC - O(n + m) | SC - O(n)

Next Greater Element II (Circular) — LC 503 🔥

Circular array → the next greater of the last element could be the first element!

Trick: Iterate the array twice (2n iterations), use i % n for circular indexing.

// LC 503. Next Greater Element II
vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> nge(n, -1);
    stack<int> st;
 
    // Two passes: Right → Left, doubled for circular
    for (int i = 2 * n - 1; i >= 0; i--) {
        while (!st.empty() && nums[st.top()] <= nums[i % n])
            st.pop();
 
        if (i < n)
            nge[i] = st.empty() ? -1 : st.top();
 
        st.push(i % n);
    }
 
    // Convert indices to values
    for (int i = 0; i < n; i++)
        nge[i] = nge[i] == -1 ? -1 : nums[nge[i]];
 
    return nge;
}
// TC - O(n) | SC - O(n)

Daily Temperatures — LC 739 🔥

“How many days until a warmer temperature?” = Next Greater Element in disguise, answer is nge[i] - i.

// LC 739. Daily Temperatures
vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> res(n, 0);
    stack<int> st;
 
    // NGE template (Right → Left)
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && temperatures[st.top()] <= temperatures[i])
            st.pop();
 
        res[i] = st.empty() ? 0 : st.top() - i;
 
        st.push(i);
    }
    return res;
}
// TC - O(n) | SC - O(n)

Online Stock Span — LC 901 🔥

“How many consecutive days the price was ≤ today?” = Previous Greater Element (strictly greater). Span = i - pge[i].

// LC 901. Online Stock Span
class StockSpanner {
    stack<pair<int, int>> st;  // {price, index}
    int idx = 0;
public:
    StockSpanner() {}
 
    int next(int price) {
        // PGE template (Left → Right, pop when <=)
        while (!st.empty() && st.top().first <= price)
            st.pop();
 
        int span = st.empty() ? idx + 1 : idx - st.top().second;
 
        st.push({price, idx});
        idx++;
        return span;
    }
};
// TC - O(1) amortized per call | SC - O(n)

6️⃣ Pattern 2 — Boundary Width (Histogram + Rain Water)

These problems use the PSE + NSE combo to find how far each bar can extend.

Key Insight

For each bar of height h[i], the width it can extend = nse[i] - pse[i] - 1 (between its left and right smaller boundaries) Area = h[i] * width

Largest Rectangle in Histogram — LC 84 🔥 📍

The classic monotonic stack problem. For each bar, find PSE and NSE, then compute area.

// LC 84. Largest Rectangle in Histogram
int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> pse(n, -1), nse(n, n);
    stack<int> st;
 
    // Single-pass: PSE + NSE merged
    for (int i = 0; i < n; i++) {
        while (!st.empty() && heights[st.top()] >= heights[i]) {
            nse[st.top()] = i;
            st.pop();
        }
 
        pse[i] = st.empty() ? -1 : st.top();
 
        st.push(i);
    }
 
    int maxArea = 0;
    for (int i = 0; i < n; i++) {
        int width = nse[i] - pse[i] - 1;
        maxArea = max(maxArea, heights[i] * width);
    }
    return maxArea;
}
// TC - O(n) | SC - O(n)

Maximal Rectangle — LC 85 💀

Convert 2D matrix to histogram per row, then apply LC 84 on each row.

// LC 85. Maximal Rectangle
int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> pse(n, -1), nse(n, n);
    stack<int> st;
 
    for (int i = 0; i < n; i++) {
        while (!st.empty() && heights[st.top()] >= heights[i]) {
            nse[st.top()] = i;
            st.pop();
        }
        pse[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
 
    int maxArea = 0;
    for (int i = 0; i < n; i++) {
        int width = nse[i] - pse[i] - 1;
        maxArea = max(maxArea, heights[i] * width);
    }
    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++) {
        // Build histogram: if '1', add to height; if '0', reset to 0
        for (int c = 0; c < cols; c++)
            heights[c] = (matrix[r][c] == '1') ? heights[c] + 1 : 0;
 
        maxArea = max(maxArea, largestRectangleArea(heights));
    }
    return maxArea;
}
// TC - O(rows * cols) | SC - O(cols)

Trapping Rain Water — LC 42 🔥 📍

Monotonic stack approach: Use a decreasing stack. When we find a taller bar, we can trap water on the popped bar using PGE (left wall) and current bar (right wall).

// LC 42. Trapping Rain Water (Monotonic Stack approach)
int trap(vector<int>& height) {
    int n = height.size();
    stack<int> st;
    int water = 0;
 
    for (int i = 0; i < n; i++) {
        while (!st.empty() && height[st.top()] <= height[i]) {
            int mid = st.top();
            st.pop();
 
            if (!st.empty()) {
                int h = min(height[st.top()], height[i]) - height[mid];
                int w = i - st.top() - 1;
                water += h * w;
            }
        }
        st.push(i);
    }
    return water;
}
// TC - O(n) | SC - O(n)

Alternative Approaches

This problem can also be solved with:

  • Two pointers — O(n) time, O(1) space (optimal)
  • Prefix max arrays — O(n) time, O(n) space The monotonic stack approach is included here as it’s a great exercise in understanding the pattern.

7️⃣ Pattern 3 — Sum of Subarray Mins / Maxs

These problems ask: “For every subarray, find the min (or max), and sum them all.”

Key Insight

Instead of iterating over all subarrays (O(n²)), ask: “How many subarrays have arr[i] as their minimum?” Answer: left[i] * right[i] where:

  • left[i] = distance from i to its PSE (or start) = i - pse[i]
  • right[i] = distance from i to its NSE (or end) = nse[i] - i

Contribution of arr[i] = arr[i] * left[i] * right[i] Total = Σ arr[i] * left[i] * right[i]

Sum of Subarray Minimums — LC 907 🔥 📍

// LC 907. Sum of Subarray Minimums
int sumSubarrayMins(vector<int>& arr) {
    int n = arr.size();
    const int MOD = 1e9 + 7;
 
    vector<int> pse(n, -1), nse(n, n);
    stack<int> st;
 
    // PSE: strictly smaller (>=) → Left → Right
    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[st.top()] >= arr[i])
            st.pop();
        pse[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
 
    while (!st.empty()) st.pop();
 
    // NSE: smaller or equal (>) → Right → Left
    // Using > (non-strict) to avoid double counting duplicates
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && arr[st.top()] > arr[i])
            st.pop();
        nse[i] = st.empty() ? n : st.top();
        st.push(i);
    }
 
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long left = i - pse[i];
        long long right = nse[i] - i;
        ans = (ans + (long long)arr[i] * left % MOD * right % MOD) % MOD;
    }
    return (int)ans;
}
// TC - O(n) | SC - O(n)

Duplicate Handling

Use >= for PSE (strictly smaller) and > for NSE (smaller or equal), or vice versa. This ensures each subarray’s minimum is counted exactly once. If both are strict (>=), subarrays where duplicates are the minimum get counted multiple times.

Sum of Subarray Maximums — Variant of LC 907

Same idea, but use PGE + NGE instead. Flip the operators.

// Sum of Subarray Maximums (variant)
long long sumSubarrayMaxs(vector<int>& arr) {
    int n = arr.size();
    const int MOD = 1e9 + 7;
 
    vector<int> pge(n, -1), nge(n, n);
    stack<int> st;
 
    // PGE: strictly greater (<=) → Left → Right
    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[st.top()] <= arr[i])
            st.pop();
        pge[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
 
    while (!st.empty()) st.pop();
 
    // NGE: greater or equal (<) → Right → Left
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && arr[st.top()] < arr[i])
            st.pop();
        nge[i] = st.empty() ? n : st.top();
        st.push(i);
    }
 
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long left = i - pge[i];
        long long right = nge[i] - i;
        ans = (ans + (long long)arr[i] * left % MOD * right % MOD) % MOD;
    }
    return ans;
}

Sum of Subarray Ranges — LC 2104 🔥

Sum of Subarray Ranges = Sum of Subarray Maximums − Sum of Subarray Minimums

// LC 2104. Sum of Subarray Ranges
long long subArrayRanges(vector<int>& nums) {
    // Answer = sumOfSubarrayMaxs - sumOfSubarrayMins
    // Use the two functions above
    return sumSubarrayMaxs(nums) - sumSubarrayMins(nums);
}
// TC - O(n) | SC - O(n)

8️⃣ Pattern 4 — Stack-Based Construction / Greedy

These problems use monotonic stacks to build an optimal sequence by deciding what to keep and what to discard.

Remove K Digits — LC 402 🔥

Make the smallest number by removing k digits. Use an increasing stack — pop larger digits when a smaller one arrives.

// LC 402. Remove K Digits
string removeKdigits(string num, int k) {
    string st;  // using string as stack for convenience
 
    for (char& c : num) {
        // Increasing stack: pop when top > current (and we still have removals left)
        while (!st.empty() && st.back() > c && k > 0) {
            st.pop_back();
            k--;
        }
        st.push_back(c);
    }
 
    // If k > 0, remove from the end (stack is increasing, largest are at end)
    while (k > 0) {
        st.pop_back();
        k--;
    }
 
    // Remove leading zeros
    int start = 0;
    while (start < st.size() && st[start] == '0') start++;
 
    string res = st.substr(start);
    return res.empty() ? "0" : res;
}
// TC - O(n) | SC - O(n)

Remove Duplicate Letters — LC 316 💀

Return the smallest subsequence with all unique characters. Monotonic increasing stack + frequency counting.

// LC 316. Remove Duplicate Letters
string removeDuplicateLetters(string s) {
    vector<int> freq(26, 0);
    vector<bool> inStack(26, false);
    string st;
 
    for (char& c : s) freq[c - 'a']++;
 
    for (char& c : s) {
        freq[c - 'a']--;
 
        if (inStack[c - 'a']) continue;
 
        // Increasing stack: pop if top > current AND top appears later
        while (!st.empty() && st.back() > c && freq[st.back() - 'a'] > 0) {
            inStack[st.back() - 'a'] = false;
            st.pop_back();
        }
 
        st.push_back(c);
        inStack[c - 'a'] = true;
    }
    return st;
}
// TC - O(n) | SC - O(1) — at most 26 chars in stack

9️⃣ Pattern 5 — Tricky / Advanced

132 Pattern — LC 456 💀

Find i < j < k with nums[i] < nums[k] < nums[j] (1-3-2 pattern).

Approach: Traverse right to left. Maintain a decreasing stack for potential “3” (nums[j]). Track the largest popped value as “2” (nums[k]). If current < “2”, we found “1”.

// LC 456. 132 Pattern
bool find132pattern(vector<int>& nums) {
    int n = nums.size();
    stack<int> st;       // decreasing stack — candidates for "3" (the largest)
    int second = INT_MIN; // the "2" in 1-3-2 (largest value popped)
 
    // Right → Left
    for (int i = n - 1; i >= 0; i--) {
        // If current < second, we found "1" < "2" < "3" ✓
        if (nums[i] < second) return true;
 
        // Pop elements smaller than current → they become candidates for "2"
        while (!st.empty() && nums[st.top()] < nums[i]) {
            second = max(second, nums[st.top()]);
            st.pop();
        }
 
        st.push(i);
    }
    return false;
}
// TC - O(n) | SC - O(n)

Why right to left?

We want to maximize “2” (nums[k]) so that it’s easier to find a “1” (nums[i]) smaller than it. Going right to left lets us build up “3” candidates and track the best “2” popped so far.

Number of Visible People in a Queue — LC 1944 💀

Person i can see person j (j > i) if everyone between them is shorter than both.

Approach: Right to left, decreasing stack. When popping (person is shorter than current), current can see them. After popping, if stack is non-empty, current can also see the stack top (the next taller person).

// LC 1944. Number of Visible People in a Queue
vector<int> canSeePersonsCount(vector<int>& heights) {
    int n = heights.size();
    vector<int> res(n, 0);
    stack<int> st;
 
    // Right → Left, strictly decreasing stack
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && heights[st.top()] < heights[i]) {
            st.pop();
            res[i]++;    // can see each person we pop
        }
 
        if (!st.empty())
            res[i]++;    // can also see the next taller/equal person
 
        st.push(i);
    }
    return res;
}
// TC - O(n) | SC - O(n)

Buildings With an Ocean View — LC 1762 ⭐

Ocean is to the right. A building has a view if all buildings to its right are shorter.

Approach: Right to left, strictly decreasing stack. At the end, everything left in the stack has an ocean view.

// LC 1762. Buildings With an Ocean View
vector<int> findBuildings(vector<int>& heights) {
    int n = heights.size();
    stack<int> st;
 
    for (int i = n - 1; i >= 0; i--) {
        // Pop buildings that are shorter or equal
        while (!st.empty() && heights[st.top()] < heights[i])
            st.pop();
 
        // Only push if this building is taller than all to its right
        if (st.empty() || heights[i] > heights[st.top()])
            st.push(i);
    }
 
    // Stack has indices in decreasing order, reverse for increasing order
    vector<int> res;
    while (!st.empty()) {
        res.push_back(st.top());
        st.pop();
    }
    reverse(res.begin(), res.end());
    return res;
}
// TC - O(n) | SC - O(n)

Sliding Window Maximum — LC 239 💀

Find the maximum in every sliding window of size k. Uses a monotonic deque (decreasing).

// LC 239. Sliding Window Maximum
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    deque<int> dq;  // decreasing deque of indices
    vector<int> res;
 
    for (int i = 0; i < n; i++) {
        // Remove elements outside the window
        while (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();
 
        // Maintain decreasing order: pop smaller elements from back
        while (!dq.empty() && nums[dq.back()] <= nums[i])
            dq.pop_back();
 
        dq.push_back(i);
 
        // Window is complete, record the max (front of deque)
        if (i >= k - 1)
            res.push_back(nums[dq.front()]);
    }
    return res;
}
// TC - O(n) | SC - O(k)

Monotonic Deque vs Stack

This is a deque (double-ended queue), not a stack. We need pop_front to expire old elements. The back of the deque works like a monotonic stack. The front gives us the window maximum.

🧠 Master Cheatsheet

Pattern Recognition

Signal in problemPattern to use
”Next greater / smaller element”Direct NGE/NSE template
”Daily temperatures” / “Stock span”Direct NGE/PGE (in disguise)
“Largest rectangle” / “Maximal rectangle”PSE + NSE → width × height
”Trapping rain water”Decreasing stack, process on pop
”Sum of subarray minimums / maximums”PSE + NSE → contribution counting
”Remove k digits” / “Smallest subsequence”Increasing stack + greedy
”132 pattern”Decreasing stack, track popped max
”Sliding window maximum”Monotonic deque (decreasing)
“Visible people in queue”Decreasing stack, count pops

The Decision Tree

Need nearest greater/smaller element?
├── Previous → traverse Left → Right, answer from stack top after popping
├── Next     → traverse Right → Left, answer from stack top after popping
│
├── Greater → pop when stack top <= current (decreasing stack)
└── Smaller → pop when stack top >= current (increasing stack)

Need both PSE + NSE (or PGE + NGE)?
└── Single-pass merged template: assign NSE inside while, PSE outside
    └── ⚠️ One will be strict, one non-strict — fine for most problems

Duplicates causing double counting?
└── Use one strict (>=) and one non-strict (>) boundary

Common Gotchas

1. Store INDICES in stack, not values → gives you position info for free
2. Default for "previous" = -1, for "next" = n (not -1!)
3. Duplicates: if both PSE and NSE are strict (>=), you'll double count
4. Circular array: iterate 2n times, use i % n
5. The condition in while loop decides the stack type:
   >= creates strictly increasing, > creates non-decreasing
   <= creates strictly decreasing, < creates non-increasing

1 item under this folder.

Mindmap

Graph View