Classic Stack Problems

1. Valid Parentheses

Problem: Given a string containing (), {}, and [], determine if it's valid.

def is_valid(s: str) -> bool:
    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

# Example
print(is_valid("()[]{}"))  # True
print(is_valid("([)]"))    # False

Key Insight: Every closing bracket must match the most recent unmatched opening bracket.

2. Evaluate Reverse Polish Notation

Problem: Evaluate arithmetic expressions in postfix notation.

def eval_rpn(tokens: list[str]) -> int:
    stack = []

    for token in tokens:
        if token in ['+', '-', '*', '/']:
            b = stack.pop()
            a = stack.pop()

            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            else:
                stack.append(int(a / b))
        else:
            stack.append(int(token))

    return stack[0]

# Example: ["2", "1", "+", "3", "*"] = (2 + 1) * 3 = 9
print(eval_rpn(["2", "1", "+", "3", "*"]))  # 9

3. Daily Temperatures

Problem: Given daily temperatures, return an array where each element is the number of days until a warmer temperature.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # Store indices

    for i in range(n):
        # While current temp is warmer than stack top
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_index = stack.pop()
            answer[prev_index] = i - prev_index

        stack.append(i)

    return answer

# Example
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]

Pattern: Use a monotonic decreasing stack to find the next greater element.

4. Min Stack (LeetCode 155)

Problem: Design a stack that supports push, pop, top, and retrieving the minimum element in O(1).

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

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack:
            self.min_stack.append(val)
        else:
            self.min_stack.append(min(val, self.min_stack[-1]))

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

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

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

5. Largest Rectangle in Histogram

Problem: Find the largest rectangle area in a histogram.

def largest_rectangle_area(heights: list[int]) -> int:
    stack = []
    max_area = 0

    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)

    # Process remaining bars
    while stack:
        height = heights[stack.pop()]
        width = len(heights) if not stack else len(heights) - stack[-1] - 1
        max_area = max(max_area, height * width)

    return max_area

Common Stack Problem Patterns

1. Matching/Validation: Parentheses, brackets, tags
2. Expression Evaluation: Infix, postfix, prefix
3. Next Greater/Smaller Element: Monotonic stacks
4. Backtracking: DFS, maze solving
5. Undo Operations: Text editors, games