Skip to main content
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 TypeStack TypeDirection
Next Greater ElementMonotonic DecreasingLeft to Right
Previous Greater ElementMonotonic DecreasingLeft to Right
Next Smaller ElementMonotonic IncreasingLeft to Right
Largest RectangleMonotonic IncreasingLeft to Right
Trapping Rain WaterEitherTwo-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

Pattern: Push opening, pop and match closingKey: Stack should be empty at end for valid input
Pattern: Monotonic increasing stackKey: Pop and calculate area when current bar is shorter
Pattern: Push numbers, pop two on operatorKey: Order matters for subtraction/division
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:
  1. Empty stack access: Always check if stack is empty before peek/pop
  2. Forgetting to process remaining: Stack may still have elements after loop
  3. Wrong monotonic direction: Know when to use increasing vs decreasing stack
  4. Not storing indices: Often need index for distance calculations

​
Debugging Checklist

1

Check Empty Stack

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

Verify Matching Logic

For parentheses: opening pushes, closing pops and compares
3

Check Remaining Elements

After loop, stack may still have unprocessed elements
4

Validate Monotonic Direction

Increasing: pop smaller, Decreasing: pop larger
5

Track Indices vs Values

For distance calculations, store indices not values

​
Interview Problems by Company

ProblemCompanyKey Concept
Valid ParenthesesAll FAANGPush open, pop close
Baseball GameAmazonStack operations
Remove Outer ParensGoogleCounter or stack
Backspace StringGoogleStack simulation

​
Interview Tips

Script for interviews:
  1. “This is a matching problem, so I’ll use a stack.”
  2. “Opening brackets push, closing brackets pop and compare.”
  3. “If match fails or stack has leftovers, it’s invalid.”
  4. “For monotonic: I maintain a stack where elements are always sorted.”
Interviewer SaysYou 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
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

ProblemDifficultyLink
Valid ParenthesesEasyLeetCode 20
Min StackMediumLeetCode 155
Daily TemperaturesMediumLeetCode 739
Largest Rectangle in HistogramHardLeetCode 84
Basic CalculatorHardLeetCode 224

​
Practice Roadmap

1

Day 1: Basic Stack

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

Day 2: Expression Evaluation

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

Day 3: Monotonic Stack

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

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.