Master Stack Patterns: 7 templates for Coding Interviews

You've spent hours poring over LeetCode, flipping between “Evaluate Reverse Polish Notation” and “Largest Rectangle in Histogram.” You memorize how to juggle parentheses, design a Min Stack, and hack your way through histogram bars. But when your Amazon interviewer asks a “simple” stack problem—with a twist—you freeze. Your brain starts frantically searching for the right formula, but everything blurs together.

Sound familiar?

Here’s the thing: It’s not your fault. Most engineers grind through 200+ problems, mistaking pattern memorization for pattern recognition. But in real interviews—especially at FAANG companies—the question won’t be copy-pasted from LeetCode. You need to spot the underlying stack pattern, adapt it, and solve any stack-flavored puzzle, even if the surface details change.

Here’s the truth: Stack patterns are the “Swiss Army knife” of coding interviews. Master the 7 core templates, and you’ll slice through 25% of all hard DSA questions at Google, Amazon, Meta, and beyond.

---

What You'll Learn

By the end of this guide, you'll master:

✅ The 7 stack sub-patterns every FAANG interviewer loves
✅ Pattern recognition skills to spot stacks hiding in complex questions
✅ 25 handpicked practice problems (with company tags!) covering every sub-pattern
✅ When to use each stack technique and how to recognize the triggers
✅ Common pitfalls and how to avoid classic stack traps
✅ A practice roadmap to go from stack newbie to interview ninja in 2-3 weeks

---

What is Stack Patterns?

Imagine you’re a chef juggling orders in a busy kitchen. Plates stack up as new tickets come in, and you always handle the last dish that arrived first. Stacks in coding interviews work the same way: LIFO (Last-In-First-Out), like a spring-loaded tray dispenser. When things get nested, reversed, or require “undo” actions, stacks shine.

The core insight: Many problems—parentheses matching, expression evaluation, histogram areas—boil down to managing order, nesting, or backtracking. Instead of brute-force trial and error, stacks let you “remember” what’s still pending and process items in just the right order.

Why This Pattern Matters

1. Optimizes Problem Solving: Converts recursive, brute-force, or O(n²) solutions into elegant O(n) stack-based approaches. This optimization is a key part of the Best Ways to Use AI for DSA and Coding Interview Preparation, where AI tools help you recognize such patterns efficiently.
2. Tests Real Engineering Skills: Interviewers use stack problems to probe your ability to reason about nested state, reversals, and memory.
3. Core to System Design: Stacks are the backbone of parsing, compilers, browser navigation, undo features, and more.
4. Heavily Featured in Interviews: Over 20% of Google and Amazon’s top DSA questions rely on stack patterns.

Companies that frequently ask stack questions: Google, Amazon, Meta (Facebook), Microsoft, Apple, ByteDance, Bloomberg, Oracle, Adobe, Roblox, Capital One, and more.

---

The 7 Stack Patterns Sub-Patterns

Let’s break down the seven essential stack sub-patterns. Each unlocks a unique set of problems and interview scenarios.

---

1. Expression Evaluation (RPN/Infix)

What it is:
Expression Evaluation problems require you to compute the value of mathematical expressions—either in infix notation (human-readable, e.g., 3 + 4 * 2) or Reverse Polish Notation (RPN, e.g., 3 4 2 * +). Stacks are used to manage operators, operands, and parentheses as you parse and evaluate the string.

Key insight:
Stacks elegantly handle precedence and nesting. For infix expressions, you use two stacks: one for numbers, one for operators. For RPN, a single operand stack suffices. This approach mirrors how calculators and compilers parse complex expressions.

How it works:

• Infix:
  1. Iterate through the tokens.
  2. Push numbers onto the number stack, operators onto the operator stack.
  3. When encountering ( or ), resolve the top of the stack as needed.
  4. At the end, resolve remaining operations.
• RPN:
  1. Iterate through tokens left to right.
  2. Push numbers onto the stack.
  3. On operator, pop operands, apply operation, push result.
  4. Final result is at the top of the stack.

When to use:

• When parsing and evaluating mathematical expressions with parentheses or mixed operator precedence.
• When the problem talks about “calculators,” “evaluate,” or “expression.”
• When you see “Reverse Polish Notation” or postfix evaluation.
• When the problem mentions “nested” or “parentheses handling” while computing values.

Recognition triggers:

• The presence of parentheses, nested expressions, or operator precedence.
• RPN or “postfix”/“prefix” keywords.
• “Design a calculator” or “evaluate an expression” instructions.

Essential Problems:
Medium:

• ⭐ Basic Calculator II – Amazon, Facebook, Microsoft, Roblox, Snapchat
  Evaluate infix expressions with +, -, *, /. Tests operator precedence handling.
• Evaluate Reverse Polish Notation – Amazon, Oracle, LinkedIn, Google, Microsoft

Hard:

• ⭐ Basic Calculator – Amazon, Roblox, Facebook, Indeed, Karat
  Handles nested parentheses and +/-. Tests deep stack recursion.
• Basic Calculator III – Facebook, Amazon, ByteDance

💡 Pro Tip:
In infix evaluation, always resolve higher precedence operators (*, /) before lower (+, -). Use helper functions to keep your parsing logic clean and modular—interviewers love well-structured code!

⚠️ Common Mistake:
Forgetting to handle parentheses or operator precedence correctly leads to wrong calculations—always test with tricky, nested cases (2*(3+(4*5))). Use stacks to defer operations until all higher-precedence or inner expressions are resolved.

Example Code Pattern:

PYTHON
Copy
def evaluate_rpn(tokens):
    stack = []
    for token in tokens:
        if token in '+-*/':
            b = stack.pop()
            a = stack.pop()
            # Apply operation
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            elif token == '/': stack.append(int(a / b))  # Truncate towards zero
        else:
            stack.append(int(token))
    return stack[0]

Typical Time/Space Complexity: O(n) time and O(n) space (where n is number of tokens).

---

2. Largest Rectangle in Histogram

What it is:
This pattern computes the area of the largest rectangle that can fit under a series of histogram bars. It generalizes to finding maximal rectangles in binary matrices. Stacks are used to efficiently track increasing bar heights and compute areas in O(n) time.

Key insight:
The stack allows you to efficiently “remember” the indices of bars in increasing order. When a lower bar is encountered, you can immediately calculate the maximal area for all taller bars to the left, without rescanning the entire array.

How it works:

1. Iterate through the histogram.
2. Push indices of increasing bar heights onto the stack.
3. When a shorter bar is found, pop from the stack and calculate area with the popped bar as the smallest height.
4. Repeat until stack is empty or a taller bar is found.
5. After the loop, process remaining bars in the stack.

When to use:

• When asked to find the “largest rectangle” under or within a histogram or matrix.
• When the problem involves “max area” under constraints.
• When you see terms like “histogram,” “rectangle,” or “maximal area.”

Recognition triggers:

• Histogram diagrams or arrays of heights.
• “Area” or “rectangle” keywords.
• Matrix problems where each row can be treated as a histogram.

Essential Problems:
Hard:

• ⭐ Largest Rectangle in Histogram – Amazon, Microsoft, Adobe, MAQ Software
  Classic. Most asked. Calculates largest rectangle in O(n) using a stack.
• Maximal Rectangle – Google, Amazon, Adobe, Bloomberg, Apple

💡 Pro Tip:
Sentinel values (a zero at the end of the histogram) help trigger processing of all remaining bars. Interviewers often ask for an extension from histogram to matrix—practice both!

⚠️ Common Mistake:
Not handling the stack until empty after the main loop, causing missed rectangles at the end. Always run a final loop to pop remaining indices and compute their areas.

Example Code Pattern:

PYTHON
Copy
def largestRectangleArea(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Sentinel to flush stack at the end
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    heights.pop()  # Clean up
    return max_area

Typical Time/Space Complexity: O(n) time, O(n) space.

---

3. Min Stack Design

What it is:
Design a stack that, in addition to push and pop, supports retrieving the minimum element in O(1) time. The core challenge is to maintain the current minimum as the stack changes.

Key insight:
Maintain an auxiliary stack that tracks the minimum at each level. Whenever you push or pop from the main stack, update the min stack accordingly. This double-stack setup ensures getMin() is always O(1).

How it works:

• Use two stacks:
  • Main stack for values
  • Min stack for the current minimum
• On push: push the value and the new min (min of current value and previous min).
• On pop: pop from both stacks.
• getMin(): return top of min stack.

When to use:

• When the problem asks for “constant time minimum” in a stack.
• When you need to design an API with push, pop, and getMin in O(1).
• When the problem says “track the min/max efficiently.”

Recognition triggers:

• “Design a stack with getMin in O(1)”
• “Track minimum/maximum during stack ops”
• “Implement an efficient stack with extra features”

Essential Problems:
Medium:

• ⭐ Min Stack – Capital One, Amazon, Bloomberg, Microsoft, Oracle
  FAANG favorite; core stack design.

Hard:

• Maximum Frequency Stack – Amazon, Microsoft, Bloomberg, Adobe
  Advanced: Supports pop by frequency, not just min/max.

💡 Pro Tip:
You can use a tuple (val, min_so_far) on the main stack instead of two stacks—this saves space and is easy to code. Explain both methods if prompted.

⚠️ Common Mistake:
Forgetting to sync the min stack on pop()—always pop from both stacks to avoid stale minimums. Test with sequences that remove the current min.

Example Code Pattern:

PYTHON
Copy
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x):
        self.stack.append(x)
        # Push new min or repeat previous min
        min_val = x if not self.min_stack else min(x, self.min_stack[-1])
        self.min_stack.append(min_val)

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_stack[-1]

Typical Time/Space Complexity: All operations O(1) time, O(n) space.

---

4. Monotonic Stack

What it is:
Monotonic stacks maintain elements in either increasing or decreasing order. They’re used to efficiently find the “next greater” or “next smaller” element for each item in an array—a frequent subroutine in interview questions.

Key insight:
A monotonic stack “remembers” the previous elements that are still competitive for the current comparison. By popping elements that can no longer be candidates, you avoid redundant checks and achieve O(n) solutions to problems that otherwise seem to require nested loops.

How it works:

• Iterate over the array:
  • While the stack is not empty and the current value is “greater” (or “smaller”) than the top, pop the stack.
  • The popped element’s answer is the current value (for next greater/smaller problems).
  • Push the current index onto the stack.
• Can be used left-to-right or right-to-left, depending on the problem.

When to use:

• When asked to find the “next greater” or “next smaller” element for each item.
• For problems about “spans”, “discounts”, or “consecutive days.”
• When you see “remove k digits,” “maximum width ramp,” or “sum of subarray minimums.”

Recognition triggers:

• “For each element, find the next greater/smaller/previous element.”
• “Discounts,” “spans,” “ramp,” or “competitive subsequence” in the prompt.
• Problems about maximizing or minimizing with respect to neighbors.

Essential Problems:
Easy:

• Final Prices With a Special Discount in a Shop – Dream11
  Apply a “discount” (next smaller to the right) for each price.
• Next Greater Element I – Amazon, Microsoft

Medium:

• ⭐ Daily Temperatures – Facebook, Bloomberg, Amazon, ByteDance, Google
  Classic. For each day, how many days to a warmer temperature?
• ⭐ Next Greater Element II – Amazon, Bloomberg, Apple, Facebook
  Handles circular arrays, next greater right.
• Find the Most Competitive Subsequence – Amazon
• Maximum Width Ramp – Facebook
• Online Stock Span – Amazon
• Remove K Digits – Amazon, Microsoft, Adobe, Oracle
• ⭐ Sum of Subarray Minimums – Google, Dunzo, Microsoft, VMware
  Find sum of minimum of every subarray using monotonic stack.

💡 Pro Tip:
Monotonic stacks are versatile—practice both increasing (for next smaller) and decreasing (for next greater) variants. For circular arrays, double the iteration or use modulo.

⚠️ Common Mistake:
Forgetting to handle remaining items in the stack at the end, leading to incomplete answers. For “next greater” problems, initialize answers to -1 or 0 as needed.

Example Code Pattern:

PYTHON
Copy
def nextGreaterElements(nums):
    n = len(nums)
    stack = []
    res = [-1] * n
    # Traverse twice for circular array
    for i in range(2 * n):
        while stack and nums[stack[-1]] < nums[i % n]:
            res[stack.pop()] = nums[i % n]
        if i < n:
            stack.append(i)
    return res

Typical Time/Space Complexity: O(n) time, O(n) space.

---

5. Simulation / Backtracking Helper

What it is:
Some problems require simulating a process or supporting backtracking—undoing or repeating actions based on certain triggers. Stacks are essential for “remembering” previous states and handling reversals, collisions, or nested actions.

Key insight:
The stack acts as a “breadcrumb trail,” storing the current path or status. When you hit an obstacle (like a collision or closing bracket), you can backtrack by popping from the stack, restoring previous context.

How it works:

• As you process the input, push relevant state onto the stack.
• On specific triggers (collision, closing, etc.), pop or modify the stack accordingly.
• The stack always represents the current valid state.

When to use:

• When the problem involves “collisions,” “undo,” or “backtracking.”
• For simulating processes with nested or reversible steps.
• When you need to maintain a “path” or “history” as you parse input.

Recognition triggers:

• “Collision,” “explode,” “decode,” or “simplify path” in the prompt.
• Problems involving reversing actions, nested states, or backtracking.

Essential Problems:
Medium:

• ⭐ Asteroid Collision – Amazon, Lyft, ByteDance, Oracle
  Simulate asteroid collisions; use stack for current survivors.
• ⭐ Decode String – Bloomberg, Google, Amazon, Oracle, ByteDance
  Decode nested repeated substrings.
• Simplify Path – Facebook, Google, Amazon, Microsoft
  Canonicalize Unix file paths by simulating directory navigation.

💡 Pro Tip:
When simulating or decoding, use tuples or objects on the stack to remember both the current context and the amount to repeat or backtrack. Diagramming the stack state helps!

⚠️ Common Mistake:
Trying to manage state with variables instead of a stack leads to messy, bug-prone code—especially with nested or recursive cases. Always use a stack to “remember” the last valid state.

Example Code Pattern:

PYTHON
Copy
def decodeString(s):
    stack = []
    curr_num = 0
    curr_str = ''
    for c in s:
        if c.isdigit():
            curr_num = curr_num * 10 + int(c)
        elif c == '[':
            stack.append((curr_str, curr_num))
            curr_str = ''
            curr_num = 0
        elif c == ']':
            prev_str, num = stack.pop()
            curr_str = prev_str + curr_str * num
        else:
            curr_str += c
    return curr_str

Typical Time/Space Complexity: O(n) time, O(n) space.

---

6. Stack - Min Stack Design

What it is:
A specialized sub-pattern focusing on designing stacks with enhanced features—most notably, tracking the minimum (or sometimes maximum) in O(1) time. This is a design-heavy interview favorite.

Key insight:
The challenge is to augment your stack so that you can answer min/max queries instantly, without scanning the stack. This is usually solved via an auxiliary stack or by storing auxiliary information alongside each value.

How it works:

• Store each value together with the minimum up to that point (tuple or object).
• On push, compare value to the current min, store both.
• On pop, remove the tuple/object.
• getMin() just reads the min from the top tuple.

When to use:

• “Design a stack with O(1) min/max.”
• When the problem asks for constant-time retrieval of min/max.
• When you need to extend stack functionality with extra features.

Recognition triggers:

• “Design a data structure…”
• “O(1) min/max/median support.”
• Follow-up questions about extending basic stack APIs.

Essential Problems:
Medium:

• ⭐ Min Stack – Capital One, Amazon, Bloomberg, Microsoft, Oracle
  The canonical O(1) min stack design problem.

💡 Pro Tip:
Explain both two-stack and single-stack (tuple/object) approaches. Interviewers often follow up with: “How would you do max? How about supporting popMin or popMax?”

⚠️ Common Mistake:
Pushing only to the main stack and forgetting the min stack causes incorrect getMin() after pops. Always keep both in sync.

Example Code Pattern:

PYTHON
Copy
class MinStack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        # Store value and min up to this point
        curr_min = x if not self.stack else min(x, self.stack[-1][1])
        self.stack.append((x, curr_min))

    def pop(self):
        self.stack.pop()

    def top(self):
        return self.stack[-1][0]

    def getMin(self):
        return self.stack[-1][1]

Typical Time/Space Complexity: O(1) per operation, O(n) space.

---

7. Valid Parentheses Matching

What it is:
This classic pattern validates whether all opening parentheses (or brackets, braces) are correctly closed and nested. Stacks are used to keep track of unmatched opening symbols.

Key insight:
Stacks mirror the natural nesting of parentheses: push for every opening, pop for every closing. If the stack is empty at the end and all pops match, the string is valid.

How it works:

• Iterate through the string:
  • Push opening symbols onto the stack.
  • On closing, pop and check for a match.
• If the stack is empty at the end, it’s valid; otherwise, invalid.

When to use:

• When asked to check for well-formed parentheses, brackets, or braces.
• When the problem asks “minimum add/remove to make valid.”
• When asked for the longest valid parentheses substring.

Recognition triggers:

• “Valid parentheses,” “well-formed,” or “balanced brackets.”
• “Minimum add/remove/swaps to balance.”
• “Longest valid substring of parentheses.”

Essential Problems:
Easy:

• ⭐ Valid Parentheses – Amazon, Bloomberg, Facebook, Apple, Microsoft
  Classic. Checks if all brackets are properly closed.

Medium:

• Minimum Add to Make Parentheses Valid – Facebook, Visa
• Minimum Number of Swaps to Make the String Balanced
• Minimum Remove to Make Valid Parentheses – Facebook, ByteDance, Bloomberg, Amazon, Goldman Sachs

Hard:

• ⭐ Longest Valid Parentheses – Amazon, Facebook, Apple, ByteDance
  Find the length of the longest valid parentheses substring.

💡 Pro Tip:
For “longest valid substring,” augment your stack to store indices, not just characters. This allows you to compute substring lengths in O(n).

⚠️ Common Mistake:
Popping from an empty stack (more closing than opening) or not checking if the stack is empty at the end. Always test edge cases like “(()” and “())”.

Example Code Pattern:

PYTHON
Copy
def isValid(s):
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in mapping.values():
            stack.append(char)
        elif char in mapping:
            if not stack or stack.pop() != mapping[char]:
                return False
    return not stack

Typical Time/Space Complexity: O(n) time, O(n) space.

---

How to Master Stack Patterns on Thita.ai

Ready to go from “I sort of get stacks” to “Bring on any stack problem”? Here’s how Thita.ai supercharges your learning:

• Pattern-Based Problem Sets:
  Practice the full Stack Patterns Sheet (/dsa-patterns-sheet) with problems grouped by sub-pattern and difficulty.

• AI Hints & Instant Feedback:
  Stuck? Get context-aware hints as you code (/code-practice), and see why your solution works (or doesn’t). This approach aligns with the Best Ways to Use AI for DSA and Coding Interview Preparation, helping you leverage AI tools effectively.

• Real Interview Simulation:
  Practice live, timed stack problems with realistic follow-ups (/ai-interview), just like in a FAANG technical screen.

• Track Your Progress:
  Visualize mastery by sub-pattern and company (/dashboard), so you know exactly where to focus next.

• Technical Coaching:
  Chat with the AI Coach (/ai-coach) to clarify doubts, get mock feedback, and learn advanced stack tricks.

---

Your Stack Patterns Learning Roadmap

Here’s a 2-3 week plan to go from stack basics to interview mastery. Each day: aim for 60-90 minutes, or more if you’re prepping full-time.

---

Week 1: Foundations

Goal: Master stack basics, monotonic stack, and parentheses validation.

• Day 1:

  • Valid Parentheses
  • Final Prices With a Special Discount in a Shop
    (Focus: Stack basics, simple monotonic)

• Day 2:

  • Next Greater Element I
  • Min Stack
    (Focus: Next greater, Min stack design)

• Day 3:

  • Minimum Add to Make Parentheses Valid
  • Minimum Remove to Make Valid Parentheses
    (Focus: Parentheses balancing, removals)

• Day 4:

  • Daily Temperatures
  • Online Stock Span
    (Focus: Monotonic stack, spans)

---

Week 2: Intermediate

Goal: Tackle expression evaluation, simulation, and advanced monotonic use.

• Day 5:

  • Basic Calculator II
  • Evaluate Reverse Polish Notation
    (Focus: Expression evaluation, infix and RPN)

• Day 6:

  • Asteroid Collision
  • Decode String
    (Focus: Simulation/backtracking with stack)

• Day 7:

  • Find the Most Competitive Subsequence
  • Remove K Digits
    (Focus: Monotonic stack for selection/optimization)

• Day 8:

  • Sum of Subarray Minimums
  • Maximum Width Ramp
    (Focus: Advanced monotonic variants)

• Day 9:

  • Mixed practice:
    • Simplify Path
    • Next Greater Element II
    • Minimum Number of Swaps to Make the String Balanced
      (Focus: Diverse stack scenarios)

---

Week 3: Mastery

Goal: Solve the hardest FAANG stack problems and build interview stamina.

• Day 10:

  • Basic Calculator
  • Basic Calculator III
    (Focus: Nested and complex expression parsing)

• Day 11:

  • Largest Rectangle in Histogram
  • Maximal Rectangle
    (Focus: Histogram to matrix area, stack in 2D)

• Day 12:

  • Maximum Frequency Stack
  • Longest Valid Parentheses
    (Focus: Advanced stack design, dynamic programming with stacks)

• Day 13:

  • Timed mixed practice:
    • 2 random medium, 1 hard
    • Use AI Interview for a full mock

• Day 14:

  • Review weaknesses on Dashboard
  • Challenge: Solve 3 stack problems in 45 min
  • Reflect with AI Coach on optimization and interview strategies

---

Common Stack Patterns Pitfalls

Let’s tackle the most frequent stack mistakes that trip up even experienced coders:

---

⚠️ 1. Not Handling Stack Empty Case
Problem:
In Valid Parentheses, popping from an empty stack causes runtime errors or false positives.

Bad code:

PYTHON
Copy
if stack.pop() != '(':
    return False

Fix: Always check if the stack is non-empty before pop!

---

⚠️ 2. Forgetting to Process the Stack After the Loop
Problem:
In Largest Rectangle in Histogram, not popping all remaining bars leaves out valid rectangles.

Bad code:

PYTHON
Copy
for i, h in enumerate(heights):
    # ...doesn't handle remaining stack after the loop!

Fix:
Add a sentinel value to flush the stack at the end.

---

⚠️ 3. Mishandling Operator Precedence
Problem:
In Basic Calculator II, applying operations in the wrong order gives incorrect results.

Bad code:

PYTHON
Copy
if token in '+-*/':
    # ...apply right away, ignores precedence!

Fix:
Use two stacks and resolve higher precedence before lower.

---

⚠️ 4. Not Handling Edge Cases in Monotonic Stack
Problem:
In Next Greater Element II, missing circular array logic.

Bad code:

PYTHON
Copy
for i in range(n):
    # ...doesn't loop twice for circularity!

Fix:
Iterate 2 * n times and use i % n indexing.

---

⚠️ 5. Not Syncing Auxiliary Stacks
Problem:
In Min Stack, forgetting to pop from the min stack leads to out-of-sync state.

Bad code:

PYTHON
Copy
def pop(self):
    self.stack.pop()
    # Forgot: self.min_stack.pop()

Fix:
Always pop from both stacks.

---

⚠️ 6. Using Variables Instead of Stack for Nested State
Problem:
In Decode String, using variables to track nested counts leads to bugs with multiple levels of nesting.

Bad code:

PYTHON
Copy
# Only one variable for num and curr_str, gets overwritten in nested cases.

Fix:
Push both string and count onto the stack at every opening bracket.

---

⚠️ 7. Not Initializing Results Properly for “Next Greater”
Problem:
In Next Greater Element I, forgetting to pre-fill answers with -1.

Fix:
Initialize with res = [-1] * n so that unanswered indices default to -1.

---

Why Stack Patterns Beat Brute Force

Let’s take Largest Rectangle in Histogram as a concrete example.

Brute Force Approach

Iterate over every possible pair of bars, compute the minimum height, and calculate area—a classic O(n²) solution.

PYTHON
Copy
def largestRectangleArea_brute(heights):
    max_area = 0
    n = len(heights)
    for i in range(n):
        min_h = heights[i]
        for j in range(i, n):
            min_h = min(min_h, heights[j])
            max_area = max(max_area, min_h * (j - i + 1))
    return max_area

Time Complexity: O(n²)
Space Complexity: O(1)

Stack Pattern Approach

Use a monotonic stack to track increasing bars and resolve areas in O(n):

PYTHON
Copy
def largestRectangleArea_stack(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Sentinel
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    heights.pop()
    return max_area

Time Complexity: O(n)
Space Complexity: O(n)

Key insight:
The stack approach processes each bar exactly twice (push and pop), never rescans the same interval. That’s a leap from O(n²) to O(n)—critical for passing FAANG interview constraints.

When does the stack pattern shine?
Whenever you’re asked for “next greater/smaller,” “largest/smallest in subarray,” or need to process nested/ordered structures. It’s the difference between a pass and a fail at Google/Amazon.

---

Beyond LeetCode: Real-World Applications

Stack patterns aren’t just for interviews—they’re everywhere in real engineering!

1. Web Browsers (Back/Forward Navigation) – Chrome, Firefox, Edge

   • Browsers use stacks to let you go “back” to previous pages and “forward” again. Each navigation action pushes or pops from the stack.

2. Expression Parsing & Compilers – Google, Microsoft, Apple

   • Compilers parse nested expressions, brackets, and scopes using stack-based parsing (shift/reduce). Bugs in this logic can break entire languages!

3. Undo/Redo Functionality – Google Docs, MS Office, Photoshop

   • Every action is pushed to a stack; Undo pops actions, Redo pushes them back. This is how “infinite undo” works.

4. Parentheses Checking in IDEs – Visual Studio Code, JetBrains

   • IDEs highlight matching parentheses/braces live as you type, using stack logic to track nesting and scope.

5. Histogram/Max Area in Image Processing – Facebook, Instagram

   • Finding the largest “block” of pixels (e.g., in object detection) uses stack-based histogram area algorithms for fast computation.

Performance benefits:
Stacks enable O(n) solutions, minimize memory, and make nested, recursive, or backtracking logic both readable and efficient.

---

Conclusion: From Memorization to Mastery

Key takeaways:

• Stack patterns are the “Swiss Army knife” of coding interviews—one tool, endless applications.
• Master the 7 sub-patterns and you’ll solve 25% of all FA