Stack Pattern

What is Stack?

Stack is a LIFO (Last In, First Out) data structure where elements are added and removed from the same end. It’s perfect for tracking “most recent” state.

Quick Recognition: Problems involving matching pairs, nested structures, “previous/next greater element”, or undo operations.

Pattern Recognition Checklist

Use Stack When

Matching parentheses/brackets/tags
Evaluating expressions (postfix/infix)
Finding next/previous greater/smaller
Processing nested structures
Implementing undo/back operations

Don't Use When

Need random access to elements
FIFO ordering needed (use Queue)
Need to process from both ends
Simple array traversal suffices

Stack Type Quick Reference

Problem Type	Stack Type	Direction
Next Greater Element	Monotonic Decreasing	Left to Right
Previous Greater Element	Monotonic Decreasing	Left to Right
Next Smaller Element	Monotonic Increasing	Left to Right
Largest Rectangle	Monotonic Increasing	Left to Right
Trapping Rain Water	Either	Two-pointer or stack

When to Use

Matching Problems

Parentheses, tags, nested structures

Expression Evaluation

Infix, postfix, prefix expressions

Monotonic Stack

Next greater/smaller element

Undo Operations

Browser history, text editors

Pattern Variations

1. Valid Parentheses

def is_valid(s):
    """Check if parentheses are balanced and properly nested"""
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping:  # Closing bracket
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
        else:  # Opening bracket
            stack.append(char)
    
    return len(stack) == 0

2. Decode String

def decode_string(s):
    """Decode strings like '3[a2[c]]' -> 'accaccacc'"""
    stack = []
    current_num = 0
    current_str = ""
    
    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == '[':
            stack.append((current_str, current_num))
            current_str = ""
            current_num = 0
        elif char == ']':
            prev_str, num = stack.pop()
            current_str = prev_str + current_str * num
        else:
            current_str += char
    
    return current_str

3. Basic Calculator

def calculate(s):
    """Evaluate expression with +, -, (, )"""
    stack = []
    result = 0
    number = 0
    sign = 1
    
    for char in s:
        if char.isdigit():
            number = number * 10 + int(char)
        elif char == '+':
            result += sign * number
            number = 0
            sign = 1
        elif char == '-':
            result += sign * number
            number = 0
            sign = -1
        elif char == '(':
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif char == ')':
            result += sign * number
            number = 0
            result *= stack.pop()  # sign
            result += stack.pop()  # previous result
    
    return result + sign * number

4. Min Stack

class MinStack:
    """Stack that supports O(1) getMin()"""
    
    def __init__(self):
        self.stack = []
        self.min_stack = []
    
    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
    
    def pop(self):
        if self.stack[-1] == self.min_stack[-1]:
            self.min_stack.pop()
        return self.stack.pop()
    
    def top(self):
        return self.stack[-1]
    
    def getMin(self):
        return self.min_stack[-1]

5. Daily Temperatures (Monotonic Stack)

def daily_temperatures(temperatures):
    """Days until warmer temperature for each day"""
    n = len(temperatures)
    result = [0] * n
    stack = []  # indices of temperatures waiting for warmer day
    
    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx
        stack.append(i)
    
    return result

Classic Problems

1. Valid Parentheses

Pattern: Push opening, pop and match closingKey: Stack should be empty at end for valid input

2. Largest Rectangle in Histogram

Pattern: Monotonic increasing stackKey: Pop and calculate area when current bar is shorter

3. Evaluate Reverse Polish Notation

Pattern: Push numbers, pop two on operatorKey: Order matters for subtraction/division

4. Simplify Path

Pattern: Split by ’/’, stack for directory navigationKey: ’..’ pops, ’.’ and ” are ignored

Monotonic Stack Deep Dive

def next_greater_element(nums):
    """For each element, find next greater element or -1"""
    result = [-1] * len(nums)
    stack = []  # Stack of indices
    
    for i in range(len(nums)):
        # Pop elements smaller than current
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    
    return result

def largest_rectangle_histogram(heights):
    """Find largest rectangle in histogram"""
    stack = []  # indices
    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)
    
    return max_area

Common Mistakes

Avoid These Pitfalls:

Empty stack access: Always check if stack is empty before peek/pop
Forgetting to process remaining: Stack may still have elements after loop
Wrong monotonic direction: Know when to use increasing vs decreasing stack
Not storing indices: Often need index for distance calculations

Debugging Checklist

Check Empty Stack

Always verify !stack.empty() before peek() or pop()

Verify Matching Logic

For parentheses: opening pushes, closing pops and compares

Check Remaining Elements

After loop, stack may still have unprocessed elements

Validate Monotonic Direction

Increasing: pop smaller, Decreasing: pop larger

Track Indices vs Values

For distance calculations, store indices not values

Interview Problems by Company

Easy
Medium
Hard

Problem	Company	Key Concept
Valid Parentheses	All FAANG	Push open, pop close
Baseball Game	Amazon	Stack operations
Remove Outer Parens	Google	Counter or stack
Backspace String	Google	Stack simulation

Problem	Company	Key Concept
Min Stack	Amazon, Bloomberg	Two stacks
Daily Temperatures	Meta, Amazon	Monotonic stack
Decode String	Google, Meta	Nested processing
Asteroid Collision	Amazon	Simulation
Evaluate RPN	Amazon	Operand stack

Problem	Company	Key Concept
Largest Rectangle	All FAANG	Monotonic increasing
Basic Calculator	Meta, Google	Two stacks
Maximal Rectangle	Google	DP + monotonic
Trapping Rain Water	All FAANG	Stack or two-pointer

Interview Tips

How to Explain Your Approach

Script for interviews:

“This is a matching problem, so I’ll use a stack.”
“Opening brackets push, closing brackets pop and compare.”
“If match fails or stack has leftovers, it’s invalid.”
“For monotonic: I maintain a stack where elements are always sorted.”

When Interviewer Says...

Interviewer Says	You Should Think
”Valid parentheses/brackets”	Basic stack push/pop
”Next greater element”	Monotonic decreasing stack
”Largest rectangle”	Monotonic increasing stack
”Evaluate expression”	Two stacks (operand + operator)
“Simplify path”	Stack for directory navigation

Monotonic Stack Template

def next_greater(arr):
    result = [-1] * len(arr)
    stack = []  # stores indices
    
    for i in range(len(arr)):
        # Pop while current is greater than stack top
        while stack and arr[i] > arr[stack[-1]]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)
    
    return result

Practice Problems

Problem	Difficulty	Link
Valid Parentheses	Easy	LeetCode 20
Min Stack	Medium	LeetCode 155
Daily Temperatures	Medium	LeetCode 739
Largest Rectangle in Histogram	Hard	LeetCode 84
Basic Calculator	Hard	LeetCode 224

Practice Roadmap

Day 1: Basic Stack

Solve: Valid Parentheses, Min Stack
Focus: Push, pop, peek operations

Day 2: Expression Evaluation

Solve: Evaluate RPN, Decode String
Focus: Operand vs operator stacks

Day 3: Monotonic Stack

Solve: Next Greater Element, Daily Temperatures
Focus: When to pop from stack

Day 4: Hard Problems

Solve: Largest Rectangle, Basic Calculator
Focus: Complex monotonic patterns

Interview Tip: When you need to track “previous” or “next” elements with certain properties, think Monotonic Stack.

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

What is Stack?

Pattern Recognition Checklist

Use Stack When

Don't Use When

Stack Type Quick Reference

When to Use

Matching Problems

Expression Evaluation

Monotonic Stack

Undo Operations

Pattern Variations

1. Valid Parentheses

2. Decode String

3. Basic Calculator

4. Min Stack

5. Daily Temperatures (Monotonic Stack)

Classic Problems

Monotonic Stack Deep Dive

Common Mistakes

Debugging Checklist

Interview Problems by Company

Interview Tips

Practice Problems

Practice Roadmap

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

​What is Stack?

​Pattern Recognition Checklist

Use Stack When

Don't Use When

​Stack Type Quick Reference

​When to Use

Matching Problems

Expression Evaluation

Monotonic Stack

Undo Operations

​Pattern Variations

​1. Valid Parentheses

​2. Decode String

​3. Basic Calculator

​4. Min Stack

​5. Daily Temperatures (Monotonic Stack)

​Classic Problems

​Monotonic Stack Deep Dive

​Common Mistakes

​Debugging Checklist

​Interview Problems by Company

​Interview Tips

​Practice Problems

​Practice Roadmap

What is Stack?

Pattern Recognition Checklist

Stack Type Quick Reference

When to Use

Pattern Variations

1. Valid Parentheses

2. Decode String

3. Basic Calculator

4. Min Stack

5. Daily Temperatures (Monotonic Stack)

Classic Problems

Monotonic Stack Deep Dive

Common Mistakes

Debugging Checklist

Interview Problems by Company

Interview Tips

Practice Problems

Practice Roadmap