Monotonic Stack — Next Smaller Element

What does it solve?

For every element in an array, find the next smaller element to its right (or none). The brute-force answer scans right from each index for O(N²). A monotonic increasing stack does it in one pass.

Key insight: keep a stack of indices whose values stay increasing from bottom to top. When the incoming value a[i] is smaller than the value on top, that top element has just found its answer: pop it and record a[i] as its next smaller. Keep popping while the top is larger, then push i. Whatever is left in the stack at the end has no smaller element to its right.

The core idea

// increasing stack of indices
res[] = -1, stack = empty
for i in 0..n-1:
  while stack && a[top] > a[i]:
    res[top] = a[i]; pop
  push i

Complexity

Time complexity

O(N)

Each index is pushed once and popped at most once. Despite the inner while loop, total pops are bounded by N, so the whole scan is linear.

Space complexity

O(N)

The stack holds at most N indices (a strictly increasing sequence), plus the result array. No nested rescans.

Examples & edge cases

Live animation — increasing stack resolves each next smaller element

resolved (answer found) in stack (waiting) not scanned yet

i (scanning) stack top popping answer recorded

Input array

Monotonic stack (bottom → top, values increasing)

Next smaller element (-1 = none)

Current step detail

i = — stack = — pops = — resolved = —

Step — of —

—

scan pointer

stack top

—

value on top

pops

—

total so far

resolved

—

answers found

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	i	a[i]	Stack (vals)	Rule	Action	Result

C++ implementation

next_smaller_element.cpp

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

// Next Smaller Element to the right via a monotonic INCREASING stack.
// The stack holds indices; their values stay increasing bottom -> top.
vector<int> nextSmaller(vector<int>& a) {
    int n = a.size();
    vector<int> res(n, -1);   // -1 = no smaller element to the right
    stack<int> st;            // stores indices

    for (int i = 0; i < n; i++) {
        // pop everything larger than a[i]: a[i] is their next smaller
        while (!st.empty() && a[st.top()] > a[i]) {
            res[st.top()] = a[i];
            st.pop();
        }
        st.push(i);              // keep the stack increasing
    }
    return res;                 // indices left in the stack keep -1
}

int main() {
    vector<int> a = {4,5,2,10,8};
    vector<int> r = nextSmaller(a);
    for (int x : r) cout << x << " "; // 2 2 -1 8 -1
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars