← All patterns

Stacks

LIFO order captures 'last-seen-first-out' semantics. Monotonic stacks find next-greater or next-smaller in O(n); expression evaluation and nested-structure validation are direct applications.

17 problems 4 Easy 7 Medium 6 Hard

Last-in-first-out semantics power matching (parentheses, expressions), monotonic-stack queries (next greater / next smaller in O(n)), DFS via explicit stack (avoid recursion depth limits), and design problems where the most-recent state must be O(1) accessible.

The monotonic-stack idiom is the workhorse: maintain a stack of indices in monotonic order; when a new element breaks monotonicity, pop and resolve. Each index enters and exits once → O(n) amortized.

When to reach for this pattern

  • Match nested / paired structures (brackets, tags)
  • Find next greater / smaller / boundary for each element
  • Expression evaluation (postfix, infix, RPN)
  • Histogram problems: largest rectangle, trapping water

Canonical template 

// monotonic decreasing stack → next greater element
vector<int> ans(n, -1);
stack<int> st;
for (int i = 0; i < (int)nums.size(); ++i) {
    while (!st.empty() && nums[st.top()] < nums[i]) {
        ans[st.top()] = nums[i];
        st.pop();
    }
    st.push(i);
}
// indices left in the stack have no next greater — already initialized to -1.

C++ · adapt the names and types to your problem.

Common pitfalls

  • Stack of indices vs stack of values — many problems need indices to compute widths
  • Strict < vs <= in monotonic stack — different problems need different conventions
  • Forgetting to flush the stack at the end if you need answers for non-popped elements
  • Iterative DFS via stack must push state explicitly — pre/in/post-order has different push patterns

Related patterns

Tree DFS Greedy Techniques Matrices

Problems (17)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.