guest@itl:~/home/data-structures$
templates/monotonic-stack.cpp
compilable
$cat templates/monotonic-stack

Monotonic Stack

Next/previous greater/smaller element queries in O(n) using a monotonic stack.

[Data Structures]|
Jul 9, 2026
|explanatory_notes.md|
#monotonic-stack#next-greater#next-smaller#stack
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;

vector<int> nextGreater(vector<int>& a, bool strict = true) {
    int n = a.size();
    vector<int> res(n, n);
    stack<int> st;
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && (strict ? a[st.top()] <= a[i] : a[st.top()] < a[i]))
            st.pop();
        if (!st.empty()) res[i] = st.top();
        st.push(i);
    }
    return res;
}

vector<int> prevGreater(vector<int>& a, bool strict = true) {
    int n = a.size();
    vector<int> res(n, -1);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && (strict ? a[st.top()] <= a[i] : a[st.top()] < a[i]))
            st.pop();
        if (!st.empty()) res[i] = st.top();
        st.push(i);
    }
    return res;
}

vector<int> nextSmaller(vector<int>& a, bool strict = true) {
    int n = a.size();
    vector<int> res(n, n);
    stack<int> st;
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && (strict ? a[st.top()] >= a[i] : a[st.top()] > a[i]))
            st.pop();
        if (!st.empty()) res[i] = st.top();
        st.push(i);
    }
    return res;
}

vector<int> prevSmaller(vector<int>& a, bool strict = true) {
    int n = a.size();
    vector<int> res(n, -1);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && (strict ? a[st.top()] >= a[i] : a[st.top()] > a[i]))
            st.pop();
        if (!st.empty()) res[i] = st.top();
        st.push(i);
    }
    return res;
}
54 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Monotonic Stack

Four functions for next/previous greater/smaller element index queries, all in O(n)O(n).

Functions

  • nextGreater(a) — for each ii, smallest j>ij > i with a[j]>a[i]a[j] > a[i] (returns nn if none)

  • prevGreater(a) — for each ii, largest j<ij < i with a[j]>a[i]a[j] > a[i] (returns −1-1 if none)

  • nextSmaller(a) — for each ii, smallest j>ij > i with a[j]<a[i]a[j] < a[i]

  • prevSmaller(a) — for each ii, largest j<ij < i with a[j]<a[i]a[j] < a[i]

    • How It Works

  • Maintain a stack of indices in monotonic order

  • New element pops all stack elements that violate the invariant — they are "blocked" and can never be answers for future elements

  • strict parameter controls ≤\le vs << comparison

    • When to Use

  • Largest rectangle in histogram

  • Stock span, daily temperatures

  • Any "nearest greater/smaller" problem

    • Complexity

  • Time — O(n)O(n) (each element pushed and popped at most once)

  • Space — O(n)O(n)