Stack

LIFO structure for problems requiring undo/redo, matching pairs, or tracking the nearest greater/smaller element. Monotonic stacks solve a class of "next greater element" problems in O(n).

// Monotonic Stack Pattern

Maintain elements in increasing or decreasing order. Pop when current element breaks the order — the popped element's "next greater/smaller" is the current element.

Easy Valid Parentheses

INSIGHT: Push open brackets. On close bracket, check if top of stack matches. If not → invalid.

def isValid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in '([{':
            stack.append(c)
        else:
            if not stack or stack[-1] != pairs[c]:
                return False
            stack.pop()
    return len(stack) == 0
# Time: O(n) | Space: O(n)

Medium Min Stack

INSIGHT: Maintain a parallel min_stack that records the current minimum at each push. They stay in sync.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    def push(self, val):
        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):
        self.stack.pop(); self.min_stack.pop()
    def top(self): return self.stack[-1]
    def getMin(self): return self.min_stack[-1]
# All operations O(1)

Medium Daily Temperatures

INSIGHT: Monotonic decreasing stack of indices. When we see a warmer temp, it resolves all colder temps in the stack.

def dailyTemperatures(temperatures):
    stack = []   # monotonic decreasing (stores indices)
    result = [0] * len(temperatures)
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            idx = stack.pop()
            result[idx] = i - idx   # days until warmer
        stack.append(i)
    return result
# Time: O(n) | Space: O(n)

Hard Largest Rectangle in Histogram

INSIGHT: Monotonic increasing stack. When a shorter bar is encountered, pop taller bars — their max extent to the right is now determined. The popped bar's left extent = where it was first pushed.

def largestRectangleArea(heights):
    stack = []   # (index, height) — monotonic increasing
    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 back to where popped bar started
        stack.append((start, h))
    for i, h in stack:
        max_area = max(max_area, h * (len(heights) - i))
    return max_area
# Time: O(n) | Space: O(n)

← Binary Search Linked List →