Cheatsheet›Stack / Monotonic Stack

CORE PATTERNVery High Frequency

Stack / Monotonic Stack

A stack processes elements in Last-In-First-Out order, making it ideal for matching brackets, evaluating expressions, and tracking the nearest relevant element. A monotonic stack extends this by maintaining elements in a strictly increasing or decreasing order, enabling O(N) solutions to 'next greater/smaller element' problems.

TimeO(N)

SpaceO(N)

DifficultyMedium

Key Insight

LIFO order turns O(N²) brute force into a single O(N) sweep.

Flip ⟲

Flip for Infographic

Interactive infographic on the flip side.

Click anywhere to Flip ⟲

FLIP SIDEStack / Monotonic Stack

Click anywhere to flip back ⟲

Recognition Signals (When to use this pattern)

→Matching or validating brackets / parentheses / tags
→Next greater / smaller element to the left or right
→Largest rectangle, area, or span in a histogram
→Evaluate or parse a mathematical expression
→Undo / redo operations or backtrack one step
→Temperatures, buildings, or stock spans — nearest dominant

Types of Problems (Subpatterns)

Each subpattern solves a specific type of problem. Click on a card to view its template.

Bracket Matching / Validity

Push opening brackets; pop and verify on every closing bracket.

Common Problems

• Valid Parentheses
• Minimum Add to Make Parentheses Valid
• Minimum Remove to Make Valid Parentheses
• Check if Tag is Valid
• Longest Valid Parentheses

5 problems

Monotonic Stack — Next Greater / Smaller

Maintain a decreasing (or increasing) stack; pop when the current element dominates.

Common Problems

• Daily Temperatures
• Next Greater Element I
• Next Greater Element II (Circular)
• Online Stock Span
• Sum of Subarray Minimums

5 problems

Largest Rectangle / Histogram

Use a monotonic stack to find, for each bar, the farthest span it can extend.

Common Problems

• Largest Rectangle in Histogram
• Maximal Rectangle
• Maximum Width Ramp
• Trapping Rain Water
• Maximum Score of a Good Subarray

5 problems

Expression Evaluation / Calculator

Use a stack to handle operator precedence and nested parentheses.

Common Problems

• Basic Calculator
• Basic Calculator II
• Basic Calculator III
• Evaluate Reverse Polish Notation
• Decode String

5 problems

Monotonic Stack — Previous Smaller / Span

Find the nearest smaller/larger element to the LEFT of each index.

Common Problems

• Sum of Subarray Minimums
• Largest Rectangle in Histogram (left boundary)
• Number of Visible People in a Queue
• Maximum Width Ramp
• 132 Pattern

5 problems

Stack for Nested / Recursive Structure

Simulate recursion iteratively — push context on entering a level, pop on leaving.

Common Problems

• Decode String
• Number of Atoms
• Mini Parser
• Flatten Nested List Iterator
• Score of Parentheses

5 problems

Template / Approach

Template for: Bracket Matching / Validity

Push on Open

Whenever you encounter an opening bracket '(', '[', or '{', push it onto the stack.

Match on Close

On a closing bracket, check that the stack is non-empty and the top matches. If not, the string is invalid.

Empty Stack = Valid

After scanning all characters, the stack must be empty — any leftovers mean unmatched openers.

template_cpp

💡 Universal bracket-matching skeleton. Works for any combination of '()', '[]', '{}'. Extend by pushing indices instead of chars when you need to locate or remove unmatched brackets.

1// Bracket matching — push openers, match on closers
2bool isValid(string s)
3{
4   stack<char> st;
5 
6   for (char c : s)
7   {
8      if (c == '(' || c == '[' || c == '{')
9      {
10         st.push(c);         // push opener
11      }
12      else
13      {
14         // closer — stack must have a matching opener
15         if (st.empty()) return false;
16 
17         char top = st.top(); st.pop();
18 
19         if ((c == ')' && top != '(') ||
20            (c == ']' && top != '[') ||
21            (c == '}' && top != '{'))
22         {
23            return false;   // mismatched pair
24         }
25      }
26   }
27 
28   return st.empty();          // all openers matched
29}

Key Idea:The stack naturally tracks 'waiting' openers. A closer either resolves the most recent opener (LIFO) or reveals a mismatch immediately — no need to scan backwards.

Practice Problems

Sharpen your skills with hand-picked problems.

View All Problems

Easy

Valid Parentheses

LeetCode #20

Medium

Minimum Add to Make Parentheses Valid

LeetCode #921

Medium

Minimum Remove to Make Valid Parentheses

LeetCode #1249

Hard

Longest Valid Parentheses

LeetCode #32

Medium

Daily Temperatures

LeetCode #739

Easy

Next Greater Element I

LeetCode #496

Medium

Next Greater Element II

LeetCode #503

Medium

Online Stock Span

LeetCode #901

Medium

Sum of Subarray Minimums

LeetCode #907

Hard

Largest Rectangle in Histogram

LeetCode #84

Hard

Maximal Rectangle

LeetCode #85

Hard

Trapping Rain Water

LeetCode #42

Hard

Maximum Score of a Good Subarray

LeetCode #1793

Medium

Evaluate Reverse Polish Notation

LeetCode #150

Hard

Basic Calculator

LeetCode #224

Medium

Basic Calculator II

LeetCode #227

Medium

132 Pattern

LeetCode #456

Medium

Maximum Width Ramp

LeetCode #962

Hard

Number of Visible People in a Queue

LeetCode #1944

Medium

Decode String

LeetCode #394

Medium

Score of Parentheses

LeetCode #856

Hard

Number of Atoms

LeetCode #726

Medium

Flatten Nested List Iterator

LeetCode #341

Stack / Monotonic Stack

1// Bracket matching — push openers, match on closers

2bool isValid(string s)

4 stack<char> st;

6 for (char c : s)

7 {

8 if (c == '(' || c == '[' || c == '{')

9 {

10 st.push(c); // push opener

11 }

12 else

13 {

14 // closer — stack must have a matching opener

15 if (st.empty()) return false;

17 char top = st.top(); st.pop();

19 if ((c == ')' && top != '(') ||

20 (c == ']' && top != '[') ||

21 (c == '}' && top != '{'))

22 {

23 return false; // mismatched pair

24 }

25 }

26 }

28 return st.empty(); // all openers matched

29}