STACK PATTERNS – COMPLETE INTERVIEW SHEET
📌 All Stack Patterns (Quick Index)
1. Monotonic Stack (Next Greater / Smaller)
2. Stock Span Pattern
3. Histogram / Area Pattern
4. Parentheses & Bracket Validation
5. Expression Evaluation Stack
6. Stack Design & Simulation
7. Stack + Greedy (Remove / Optimize)
8. Stack + String Processing
9. Contribution / Subarray Stack
10. Stack for DFS / Iterative Traversal
1️⃣ Monotonic Stack (Next Greater / Smaller)
When to use
• Next / Previous greater or smaller element
• First element on left/right satisfying condition
Questions
• Next Greater Element I
[Link]
Companies: Amazon, Microsoft, Google
• Next Greater Element II
[Link]
Companies: Google, Amazon
• Daily Temperatures
[Link]
Companies: Amazon, Meta, Microsoft
• Next Smaller Element (GFG)
[Link]
Companies: Amazon, Flipkart
2️⃣ Stock Span Pattern
When to use
• Count consecutive previous elements
1
• Span or streak based logic
Questions
• Online Stock Span
[Link]
Companies: Amazon, Microsoft
• Stock Span Problem (GFG)
[Link]
Companies: Flipkart, Infosys
• Number of Visible People in a Queue
[Link]
Companies: Google
3️⃣ Histogram / Area Pattern
When to use
• Maximum area / rectangle problems
• Expand left and right boundaries
Questions
• Largest Rectangle in Histogram
[Link]
Companies: Google, Amazon, Uber
• Maximal Rectangle
[Link]
Companies: Amazon, Microsoft
• Trapping Rain Water
[Link]
Companies: Google, Meta
• Sum of Subarray Minimums
[Link]
Companies: Amazon
4️⃣ Parentheses & Bracket Validation
When to use
• Balanced or nested structures
2
Questions
• Valid Parentheses
[Link]
Companies: Amazon, Microsoft, PayPal
• Longest Valid Parentheses
[Link]
Companies: Google
• Minimum Add to Make Parentheses Valid
[Link]
Companies: Adobe
• Remove Invalid Parentheses
[Link]
Companies: Meta
5️⃣ Expression Evaluation Stack
When to use
• Infix / Prefix / Postfix expressions
• Operator precedence
Questions
• Evaluate Reverse Polish Notation
[Link]
Companies: Amazon, Oracle
• Basic Calculator II
[Link]
Companies: Uber, Airbnb
• Basic Calculator
[Link]
Companies: Google
6️⃣ Stack Design & Simulation
When to use
• Custom stack behavior
• Extra operations in O(1)
3
Questions
• Min Stack
[Link]
Companies: Amazon, Google
• Max Stack
[Link]
Companies: LinkedIn
• Implement Queue using Stacks
[Link]
Companies: Amazon, Infosys
• Implement Stack using Queues
[Link]
Companies: TCS
7️⃣ Stack + Greedy (Remove / Optimize)
When to use
• Remove elements to get optimal result
Questions
• Remove K Digits
[Link]
Companies: Google, Amazon
• Remove Duplicate Letters
[Link]
Companies: Meta
• Make The String Great
[Link]
Companies: Amazon
• Smallest Subsequence of Distinct Characters
[Link]
Companies: Google
8️⃣ Stack + String Processing
When to use
• Undo / backspace
• Pattern removal
4
Questions
• Backspace String Compare
[Link]
Companies: Adobe
• Simplify Path
[Link]
Companies: Airbnb
• Decode String
[Link]
Companies: Microsoft
• Remove All Adjacent Duplicates II
[Link]
Companies: Amazon
9️⃣ Contribution / Subarray Stack
When to use
• Each element contributes as min/max
Questions
• Sum of Subarray Minimums
[Link]
Companies: Amazon
• Sum of Subarray Ranges
[Link]
Companies: Google
• Subarray Minimums (GFG)
[Link]
Companies: Flipkart
🔟 Stack for DFS / Iterative Traversal
When to use
• Replace recursion
• Explicit stack control
5
Questions
• Binary Tree Inorder Traversal (Iterative)
[Link]
Companies: Amazon, Microsoft
• DFS of Graph (Iterative – GFG)
[Link]
Companies: Google
• Clone Graph
[Link]
Companies: Meta
✅ How to Use This Sheet
• Patterns 1–4 → Core stack mastery
• Patterns 5–7 → FAANG depth
• All patterns → Interview-proof