Stacks

Pre-requisite: [[Stack & Queue]] — covers Stack/Queue data structure, operations, Python implementation

---

When to Use

• Need to track the most recent element seen (last-in, first-out)
• Matching/validation — brackets, tags, parentheses
• Next greater / next smaller element in an array
• Previous state needs to be restored (undo, backtracking)
• Problem involves ranges where you need to know what's been seen so far

Signal phrases: "nearest", "next greater", "previous smaller", "valid parentheses", "temperature warmer", "rectangle area"

---

Patterns

1. Bracket Matching / Validation

Push opening brackets, pop when closing bracket is found. If mismatch or stack not empty at end → invalid.

def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}
    for c in s:
        if c in '({[':
            stack.append(c)
        elif not stack or stack[-1] != pairs[c]:
            return False
        else:
            stack.pop()
    return not stack

Key insight: Map closing → opening in a dict. Check stack[-1] before popping.

---

2. Min/Max Stack

Maintain a parallel min_stack that tracks the running minimum at every state. Both stacks push/pop together.

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

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

    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]

Key insight: min_stack[i] = minimum of all values from bottom up to index i. Never just store the current min — you need history for when values are popped.

---

3. Monotonic Decreasing Stack (Next Greater Element)

Keep stack in decreasing order — when a larger element arrives, pop everything smaller. Those popped elements have found their "next greater".

# LC 739 — Daily Temperatures
def dailyTemperatures(temperatures: list[int]) -> list[int]:
    result = [0] * len(temperatures)
    stack = []  # stores indices

    for i, t in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < t:
            idx = stack.pop()
            result[idx] = i - idx   # days until warmer
        stack.append(i)

    return result

Template (Next Greater Element):

stack = []
for i, val in enumerate(arr):
    while stack and arr[stack[-1]] < val:   # decreasing: pop when curr is bigger
        idx = stack.pop()
        # arr[idx]'s next greater element is val
    stack.append(i)
# anything left in stack has no next greater element

Monotonic Increasing Stack (Next Smaller Element) — just flip the comparison: arr[stack[-1]] > val.

---

4. Monotonic Stack — Largest Rectangle (Hard)

Track indices where you can extend a rectangle backwards. When a shorter bar arrives, calculate areas for all taller bars behind it.

# LC 84 — Largest Rectangle in Histogram
def largestRectangleArea(heights: list[int]) -> int:
    stack = []   # (start_index, height)
    max_area = 0

    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            max_area = max(max_area, height * (i - idx))
            start = idx           # can extend this bar back to where taller bar started
        stack.append((start, h))

    for idx, height in stack:     # remaining bars extend to the end
        max_area = max(max_area, height * (len(heights) - idx))

    return max_area

Key insight: When you pop, the width isn't just 1 — it extends back to where that bar could have started (start = idx).

---

5. Stack for Ordering / Grouping (Car Fleet)

Sort by position (reverse). Use arrival time as a proxy — if a car arrives before the car ahead, it merges into that fleet. Stack stores fleet arrival times.

# LC 853 — Car Fleet
def carFleet(target: int, position: list[int], speed: list[int]) -> int:
    pairs = sorted(zip(position, speed), reverse=True)  # closest to target first
    stack = []

    for pos, spd in pairs:
        time = (target - pos) / spd
        if not stack or time > stack[-1]:   # takes longer → new fleet
            stack.append(time)
        # if time <= stack[-1], this car catches up → same fleet, don't push

    return len(stack)

Key insight: Sort closest-to-target first. A car that arrives faster than the car ahead merges into its fleet — only slower/equal cars create new fleets.

---

6. Implicit Stack — Recursion & DFS

Every recursive call uses the call stack implicitly. DFS on trees/graphs is the most common pattern.

# Iterative DFS using explicit stack (avoids recursion limit)
def dfs(graph, start):
    stack = [start]
    visited = set()
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            stack.append(neighbor)

---

Key Problems

---

Complexity

The monotonic stack is O(n) even though there's a while loop — each element is pushed and popped at most once total across all iterations.