DSA Patterns - Code Library

Runnable Python implementations of the core interview patterns. Each file has a header (difficulty, when-to-use, common mistakes) and a __main__ demo. Source lives in DSA/patterns/.

Use the copy button on any block to grab the code. These embed the real source files, so they always match the repo.

Backtracking

# PATTERN NAME: Backtracking
# DIFFICULTY: Medium | FREQUENCY: Very High (subsets, permutations, combinations at all companies)

# WHEN TO USE:
# - Generate all combinations / permutations / subsets.
# - Constraint satisfaction (N-Queens, Sudoku).
# - Path finding with all solutions.
# - "Find all ways to..." problems.

# CORE IDEA (INTUITION):
# - Build the solution incrementally, one choice at a time.
# - Explore a choice (recurse), then UNDO it (backtrack) to try the next.
# - Prune branches that cannot lead to a valid solution.
# - Template: choose -> explore -> unchoose.

# INVARIANTS:
# - The current path always represents a valid partial solution.
# - After exploring a choice, state is restored exactly (undo the choice).
# - Base case captures a complete solution.

# COMMON MISTAKES:
# - Forgetting to undo the choice (state leaks between branches).
# - Appending a reference to the mutable path instead of a copy (path[:]).
# - Wrong start index for combinations (causes duplicates or misses).
# - Not skipping duplicates when the input has repeats.

# TIME & SPACE:
# - Subsets: O(2^n) subsets, O(n) per subset.
# - Permutations: O(n! * n).
# - Combinations: O(C(n, k) * k).
# - Space: O(n) recursion depth (excluding output).

# RELATED PROBLEMS:
# - Subsets (LC 78) / Subsets II (LC 90)
# - Permutations (LC 46) / Permutations II (LC 47)
# - Combination Sum (LC 39) / Combination Sum II (LC 40)
# - N-Queens (LC 51)
# - Word Search (LC 79)
# - Palindrome Partitioning (LC 131)


# === SUBSETS ===
def subsets(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []

    def backtrack(start: int, path: list[int]) -> None:
        result.append(path[:])  # every path is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])     # choose
            backtrack(i + 1, path)   # explore
            path.pop()               # unchoose

    backtrack(0, [])
    return result


# === PERMUTATIONS ===
def permute(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []

    def backtrack(path: list[int], used: list[bool]) -> None:
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used[i] = False

    backtrack([], [False] * len(nums))
    return result


# === COMBINATION SUM (unlimited reuse) ===
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    result: list[list[int]] = []

    def backtrack(start: int, path: list[int], remaining: int) -> None:
        if remaining == 0:
            result.append(path[:])
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i (not i+1): reuse allowed
            path.pop()

    backtrack(0, [], target)
    return result


# === SUBSETS II (with duplicates) ===
def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    nums.sort()

    def backtrack(start: int, path: list[int]) -> None:
        result.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue  # skip duplicates at the same level
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result


# === N-QUEENS (count solutions) ===
def total_n_queens(n: int) -> int:
    cols: set[int] = set()
    diag1: set[int] = set()  # r - c
    diag2: set[int] = set()  # r + c
    count = 0

    def backtrack(row: int) -> None:
        nonlocal count
        if row == n:
            count += 1
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            backtrack(row + 1)
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return count


if __name__ == "__main__":
    print(subsets([1, 2, 3]))
    # [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
    print(permute([1, 2, 3]))
    # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    print(combination_sum([2, 3, 6, 7], 7))    # [[2, 2, 3], [7]]
    print(subsets_with_dup([1, 2, 2]))         # [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
    print(total_n_queens(4))                   # 2

Bfs Patterns

# PATTERN NAME: Breadth-First Search (BFS)
# DIFFICULTY: Medium | FREQUENCY: Very High (shortest path, level order, grid BFS at all companies)

# WHEN TO USE:
# - Shortest path in unweighted graphs or grids.
# - Level-order traversal of trees.
# - Finding connected components in graphs.
# - Explore all neighbors before going deeper.
# - Examples: Shortest Path in a Grid, Word Ladder, Clone Graph.

# CORE IDEA (INTUITION):
# - Explore all neighbors at the current depth before moving to the next level.
# - Use a queue (collections.deque) to track nodes to visit next.
# - Mark nodes visited to avoid cycles and redundant work.

# INVARIANTS:
# - All nodes at the current depth are processed before the next depth.
# - Each node is visited at most once.
# - The queue maintains exploration order.
# - Distance from the start to any node is minimized (unweighted).

# COMMON MISTAKES:
# - Not marking nodes visited, leading to infinite loops.
# - Forgetting grid boundary checks.
# - Not handling the case when start == target.
# - Mixing up row and column indices.
# - Using list.pop(0) (O(n)) instead of deque.popleft().

# TIME & SPACE:
# - Time: O(V + E) (or O(m*n) on a grid).
# - Space: O(V) for the queue and visited set.

# RELATED PROBLEMS:
# - Word Ladder (LC 127)
# - Clone Graph (LC 133)
# - Rotting Oranges (LC 994)
# - Shortest Path in Binary Matrix (LC 1091)
# - Shortest Path in a Grid with Obstacles Elimination (LC 1293)
# - Sliding Puzzle (LC 773)

from collections import deque


# EXAMPLE: Shortest Path in a Grid with Obstacles Elimination
# State includes remaining eliminations, so the visited key is (row, col, remaining).
def shortest_path(grid: list[list[int]], k: int) -> int:
    m, n = len(grid), len(grid[0])

    q: deque[tuple[int, int, int, int]] = deque()
    q.append((0, 0, 0, k))  # (row, col, steps, remaining eliminations)

    visited = {(0, 0, k)}
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    while q:
        row, col, steps, remaining = q.popleft()

        if row == m - 1 and col == n - 1:
            return steps

        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            if new_row < 0 or new_col < 0 or new_row >= m or new_col >= n:
                continue

            new_remaining = remaining - grid[new_row][new_col]
            key = (new_row, new_col, new_remaining)
            if new_remaining >= 0 and key not in visited:
                visited.add(key)
                q.append((new_row, new_col, steps + 1, new_remaining))

    return -1


if __name__ == "__main__":
    grid = [[0, 0, 0], [1, 1, 0], [0, 0, 0], [0, 1, 1], [0, 0, 0]]
    print(shortest_path(grid, 1))  # 6

Binary Search

# PATTERN NAME: Binary Search
# DIFFICULTY: Medium | FREQUENCY: Very High (search + binary-search-on-answer at all companies)

# WHEN TO USE:
# - Searching in a sorted array or range.
# - Finding an element, boundary conditions, or optimal values (binary search on the answer).

# CORE IDEA (INTUITION):
# - Repeatedly divide the search interval in half.
# - Compare the target to the middle element.
# - Narrow the search to the left or right half based on the comparison.

# INVARIANTS:
# - The array/range is sorted (or the predicate is monotonic).
# - The search space halves each step.
# - The answer, if present, remains within the search space.

# COMMON MISTAKES:
# - Not updating left/right pointers correctly (infinite loop).
# - Off-by-one errors in mid or in the loop condition (< vs <=).
# - Not handling edge cases (single-element array, empty array).
# - For "binary search on answer": wrong feasibility predicate.

# TIME & SPACE:
# - Time: O(log n) (times O(n) predicate cost for search-on-answer variants).
# - Space: O(1).

# RELATED PROBLEMS:
# - Find Peak Element (LC 162)
# - Kth Missing Positive Number (LC 1539)
# - Capacity To Ship Packages Within D Days (LC 1011)
# - Median of Two Sorted Arrays (LC 4)
# - Kth Smallest Element in a Sorted Matrix (LC 378)


# EXAMPLE: Find Peak Element
# A peak element is strictly greater than its neighbors: nums[i] > nums[i-1] and nums[i] > nums[i+1].
def find_peak_element(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1

    while left < right:
        mid = (left + right) // 2
        # If mid < next, a peak must be on the right; otherwise on the left (including mid).
        if nums[mid] < nums[mid + 1]:
            left = mid + 1
        else:
            right = mid

    return left  # left == right points to a peak


# EXAMPLE: Kth Missing Positive Number
# Missing count before arr[mid] = arr[mid] - (mid + 1) (expected value if nothing were missing).
def find_kth_positive(arr: list[int], k: int) -> int:
    l, r = 0, len(arr)

    while l < r:
        mid = (l + r) // 2
        missing = arr[mid] - (mid + 1)
        if missing < k:
            l = mid + 1  # not enough missing yet, search right
        else:
            r = mid       # too many missing (or exactly k), search left

    # l = index where the kth missing number would be inserted; answer = l + k
    return l + k


# EXAMPLE: Capacity To Ship Packages Within D Days
# Binary search on capacity in [max(weights), sum(weights)].
def ship_within_days(weights: list[int], days: int) -> int:
    def can_ship(capacity: int) -> bool:
        days_needed = 1
        current_load = 0
        for w in weights:
            if current_load + w > capacity:
                days_needed += 1
                current_load = w
            else:
                current_load += w
        return days >= days_needed

    i, j = max(weights), sum(weights)
    while i < j:
        cap = (i + j) // 2
        if can_ship(cap):
            j = cap
        else:
            i = cap + 1
    return i


# EXAMPLE: Median in a Row-Wise Sorted Matrix
# Binary search on the VALUE range; count elements <= mid across rows.
def median(mat: list[list[int]]) -> int:
    m, n = len(mat), len(mat[0])

    low = min(mat[i][0] for i in range(m))
    high = max(mat[i][n - 1] for i in range(m))

    target = (m * n) // 2 + 1  # median has this many elements <= it

    def count_le(arr: list[int], limit: int) -> int:
        # number of elements <= limit in a sorted row (upper bound)
        left, right = 0, len(arr)
        while left < right:
            mid = (left + right) // 2
            if arr[mid] <= limit:
                left = mid + 1
            else:
                right = mid
        return left

    while low <= high:
        mid = (low + high) // 2
        count = sum(count_le(mat[i], mid) for i in range(m))
        if count < target:
            low = mid + 1
        else:
            high = mid - 1

    return low


# EXAMPLE: Median of Two Sorted Arrays
# Binary search on the smaller array's partition -> O(log(min(m, n))).
def find_median_sorted_arrays(nums1: list[int], nums2: list[int]) -> float:
    if len(nums1) > len(nums2):
        return find_median_sorted_arrays(nums2, nums1)

    A, B = nums1, nums2
    m, n = len(A), len(B)
    total = m + n
    half = total // 2

    l, r = 0, m - 1
    while True:
        i = (l + r) // 2            # last index on A's left partition
        j = half - (i + 1) - 1      # last index on B's left partition

        a_left = A[i] if i >= 0 else float("-inf")
        a_right = A[i + 1] if i + 1 < m else float("inf")
        b_left = B[j] if j >= 0 else float("-inf")
        b_right = B[j + 1] if j + 1 < n else float("inf")

        if a_left <= b_right and b_left <= a_right:
            if total % 2 == 0:
                return (max(a_left, b_left) + min(a_right, b_right)) / 2
            return min(a_right, b_right)
        elif a_left > b_right:
            r = i - 1  # took too many from A -> move left
        else:
            l = i + 1  # took too few from A -> move right


if __name__ == "__main__":
    print(find_peak_element([1, 2, 3, 1]))                 # 2
    print(find_kth_positive([2, 3, 4, 7, 11], 5))          # 9
    print(ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))  # 15
    print(median([[1, 3, 5], [2, 6, 9], [3, 6, 9]]))       # 5
    print(find_median_sorted_arrays([1, 3], [2]))          # 2
    print(find_median_sorted_arrays([1, 2], [3, 4]))       # 2.5

Bit Manipulation

# PATTERN NAME: Bit Manipulation
# DIFFICULTY: Medium | FREQUENCY: High (XOR tricks, masks, single-number at Google/Amazon)

# WHEN TO USE:
# - Space-optimized flags/sets (bitmask).
# - Finding unique/missing numbers (XOR tricks).
# - Subset generation via bitmask.
# - Counting bits, power-of-two checks.

# CORE IDEA (INTUITION):
# - Numbers are sequences of bits; use bitwise ops to manipulate them directly.
# - XOR: a ^ a = 0, a ^ 0 = a  (cancels pairs).
# - AND with (1 << i): check the i-th bit.
# - OR with (1 << i): set the i-th bit.
# - n & (n - 1): clears the lowest set bit.

# COMMON OPERATIONS:
# - Check i-th bit:  (num >> i) & 1
# - Set i-th bit:    num | (1 << i)
# - Clear i-th bit:  num & ~(1 << i)
# - Toggle i-th bit: num ^ (1 << i)
# - Lowest set bit:  num & (-num)
# - Clear lowest set bit: num & (num - 1)

# COMMON MISTAKES:
# - Python ints are arbitrary precision (no 32-bit overflow); mask with & 0xFFFFFFFF when a
#   fixed-width result is required (e.g. LC 371 "Sum of Two Integers").
# - Operator precedence: bitwise ops are lower than comparison; parenthesize.
# - Confusing logical (and/or) with bitwise (&/|).

# TIME & SPACE:
# - Most bit operations: O(1) or O(number of bits) = O(32).
# - Subset generation: O(2^n).

# RELATED PROBLEMS:
# - Single Number (LC 136) / Single Number II (LC 137) / III (LC 260)
# - Number of 1 Bits (LC 191)
# - Counting Bits (LC 338)
# - Missing Number (LC 268)
# - Subsets (LC 78) - bitmask approach
# - Power of Two (LC 231)


# Single Number - every element appears twice except one (XOR cancels pairs)
def single_number(nums: list[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result


# Number of 1 Bits (Hamming weight) - Brian Kernighan's algorithm
def hamming_weight(n: int) -> int:
    count = 0
    while n:
        n &= n - 1  # clear the lowest set bit
        count += 1
    return count


# Counting Bits - count set bits for every number 0..n
# dp[i] = dp[i >> 1] + (i & 1)
def count_bits(n: int) -> list[int]:
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp


# Missing Number - XOR all indices and values
def missing_number(nums: list[int]) -> int:
    missing = len(nums)
    for i, num in enumerate(nums):
        missing ^= i ^ num
    return missing


# Power of Two - a power of two has exactly one set bit
def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0


# Generate all subsets using bitmask
def subsets_bitmask(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    result: list[list[int]] = []

    for mask in range(1 << n):  # 2^n masks
        subset: list[int] = []
        for i in range(n):
            if mask & (1 << i):  # is the i-th bit set?
                subset.append(nums[i])
        result.append(subset)

    return result


# Sum of Two Integers without + or - (mask to 32 bits)
def get_sum(a: int, b: int) -> int:
    mask = 0xFFFFFFFF
    while b & mask:
        carry = (a & b) << 1
        a = a ^ b
        b = carry
    a &= mask
    # handle negative results (32-bit two's complement)
    return a if a <= 0x7FFFFFFF else ~(a ^ mask)


if __name__ == "__main__":
    print(single_number([4, 1, 2, 1, 2]))   # 4
    print(hamming_weight(11))                # 3 (1011)
    print(count_bits(5))                     # [0, 1, 1, 2, 1, 2]
    print(missing_number([3, 0, 1]))         # 2
    print(is_power_of_two(16))               # True
    print(is_power_of_two(18))               # False
    print(subsets_bitmask([1, 2, 3]))
    # [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
    print(get_sum(2, 3))                     # 5

Boyer Moore Majority Voting

# PATTERN NAME: Boyer-Moore Majority Voting
# DIFFICULTY: Easy | FREQUENCY: High (majority element n/2 and n/3 at Google/Amazon/Adobe)

# WHEN TO USE:
# - Finding the majority element (appears more than n/2 times) in O(1) space.
# - Extended form: elements appearing more than n/k times (keep k-1 candidates).

# CORE IDEA (INTUITION):
# - Track a candidate and a counter.
# - Increment on a match, decrement on a mismatch; when the counter hits 0, pick a new candidate.
# - After one pass, the surviving candidate is the majority element (if one exists).

# INVARIANTS:
# - A true majority element appears more than n/2 times.
# - The counter reflects the balance between the candidate and everything else.
# - When count is 0, the current candidate cannot be the majority.

# COMMON MISTAKES:
# - Assuming a majority element exists without verifying (needed for the n/3 variant).
# - Not resetting the count when choosing a new candidate.
# - Misreading the counter's role in tracking dominance.

# TIME & SPACE:
# - Time: O(n).
# - Space: O(1).

# RELATED PROBLEMS:
# - Majority Element (LC 169)
# - Majority Element II (LC 229) - elements appearing more than n/3 times


# EXAMPLE: Majority Element (appears more than floor(n/2) times; assumed to exist).
def majority_element(nums: list[int]) -> int | None:
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate


# EXAMPLE: Majority Element II (more than floor(n/3) times -> at most 2 such elements).
def majority_element_ii(nums: list[int]) -> list[int]:
    candidate1 = candidate2 = None
    count1 = count2 = 0

    for num in nums:
        if num == candidate1:
            count1 += 1
        elif num == candidate2:
            count2 += 1
        elif count1 == 0:
            candidate1 = num
            count1 = 1
        elif count2 == 0:
            candidate2 = num
            count2 = 1
        else:
            count1 -= 1
            count2 -= 1

    # Verify candidates (no guarantee they exceed n/3)
    count1 = sum(1 for num in nums if num == candidate1)
    count2 = sum(1 for num in nums if num == candidate2)

    result: list[int] = []
    if count1 > len(nums) // 3:
        result.append(candidate1)
    if count2 > len(nums) // 3:
        result.append(candidate2)
    return result


if __name__ == "__main__":
    print(majority_element([2, 2, 1, 1, 1, 2, 2]))  # 2
    print(majority_element_ii([3, 2, 3]))            # [3]
    print(majority_element_ii([1, 1, 1, 3, 3, 2, 2, 2]))  # [1, 2]

Cycle Detection Directed Graph

# PATTERN NAME: Cycle Detection in a Directed Graph
# DIFFICULTY: Medium | FREQUENCY: Very High (course schedule, dependency resolution at all companies)

# WHEN TO USE:
# - Directed graphs where you must detect cycles.
# - Course scheduling with prerequisites.
# - Dependency resolution, topological sort applicability.

# CORE IDEA (INTUITION):
# - DFS with three states per node: UNVISITED, VISITING, VISITED.
# - Reaching a node currently in the VISITING state means a back edge -> cycle.

# INVARIANTS:
# - Each node is UNVISITED, VISITING, or VISITED.
# - A cycle is detected if a VISITING node is revisited on the current path.
# - Fully explored nodes become VISITED and are skipped later.

# COMMON MISTAKES:
# - Using a single visited set (works for undirected, not directed).
# - Forgetting to reset/track the VISITING state (recursion stack).
# - Not iterating over all nodes for disconnected graphs.
# - Misreading edge direction when building the graph.

# TIME & SPACE:
# - Time: O(V + E).
# - Space: O(V) for the recursion stack and state array.

# RELATED PROBLEMS:
# - Course Schedule (LC 207)
# - Course Schedule II (LC 210)
# - Find Eventual Safe States (LC 802)
# - Alien Dictionary (LC 269)

# NOTE: This file is the PATTERN applied to a concrete problem (Course Schedule). For the bare
# 3-color cycle-detection algorithm (set-based, generic graph), see
# algorithms/graph/cycle_detection_directed.py. This version uses an int state[] array keyed by
# course index - the same idea, shaped for the LC 207/210 input format.


# EXAMPLE: Course Schedule - can all courses be finished (is the graph acyclic)?
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    graph: list[list[int]] = [[] for _ in range(num_courses)]
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    UNVISITED, VISITING, VISITED = 0, 1, 2
    state = [UNVISITED] * num_courses

    def has_cycle(course: int) -> bool:
        if state[course] == VISITING:
            return True   # cycle detected
        if state[course] == VISITED:
            return False  # already fully explored

        state[course] = VISITING
        for neighbor in graph[course]:
            if has_cycle(neighbor):
                return True
        state[course] = VISITED
        return False

    for course in range(num_courses):
        if has_cycle(course):
            return False
    return True


# (Network Delay Time / Dijkstra was moved out of this file - it's a shortest-path problem, not
# cycle detection. See algorithms/graph/dijkstra.py for Dijkstra and its Network Delay Time variant.)


if __name__ == "__main__":
    print(can_finish(2, [[1, 0]]))            # True
    print(can_finish(2, [[1, 0], [0, 1]]))    # False

Dfs Patterns

# PATTERN NAME: Depth-First Search (DFS)
# DIFFICULTY: Medium | FREQUENCY: Very High (connected components, backtracking, topo at all companies)

# WHEN TO USE:
# - Traversal of trees or graphs.
# - Backtracking problems (permutations, combinations, N-Queens).
# - Pathfinding, topological sorting, connected components.
# - Examples: Number of Islands, Word Search, Course Schedule.

# CORE IDEA (INTUITION):
# - Explore as far as possible along each branch before backtracking.
# - Use recursion or an explicit stack.
# - Mark nodes visited to avoid cycles and redundant work.

# INVARIANTS:
# - Each node is visited exactly once.
# - The recursion/explicit stack maintains the current path.
# - Backtracking occurs when all neighbors are explored.

# COMMON MISTAKES:
# - Not marking nodes visited (infinite loops).
# - Forgetting to backtrack properly in recursive calls.
# - Not handling disconnected components.
# - Using DFS where BFS is better (shortest path in unweighted graphs).
# - Recursion depth limits on large graphs.

# TIME & SPACE:
# - Time: O(V + E).
# - Space: O(V) for the recursion stack and visited set.

# RELATED PROBLEMS:
# - Number of Provinces (LC 547)
# - Course Schedule IV (LC 1462)
# - Number of Islands (LC 200)
# - Clone Graph (LC 133)
# - Graph Coloring / M-Coloring (classic)


# EXAMPLE: Number of Provinces (connected components in an adjacency matrix)
def find_circle_num(is_connected: list[list[int]]) -> int:
    n = len(is_connected)
    visited = [False] * n
    provinces = 0

    def dfs(city: int) -> None:
        visited[city] = True
        for i in range(n):
            if is_connected[city][i] == 1 and not visited[i]:
                dfs(i)

    for i in range(n):
        if not visited[i]:
            dfs(i)          # explore the whole component
            provinces += 1  # count it as one province

    return provinces


# EXAMPLE: Course Schedule IV (transitive prerequisites via memoized DFS)
def check_if_prerequisite(num_courses: int, prerequisites: list[list[int]],
                          queries: list[list[int]]) -> list[bool]:
    graph: list[list[int]] = [[] for _ in range(num_courses)]
    for pre, course in prerequisites:
        graph[course].append(pre)

    pre_map: dict[int, set[int]] = {}

    def dfs(course: int) -> set[int]:
        if course in pre_map:
            return pre_map[course]
        pre_set: set[int] = set()
        for nei in graph[course]:
            pre_set.add(nei)
            pre_set |= dfs(nei)  # transitive prerequisites
        pre_map[course] = pre_set
        return pre_set

    for i in range(num_courses):
        dfs(i)

    return [pre in pre_map.get(course, set()) for pre, course in queries]


# EXAMPLE: M-Coloring Problem (DFS + backtracking)
def graph_coloring(v: int, edges: list[list[int]], m: int) -> bool:
    graph: list[list[int]] = [[] for _ in range(v)]
    for u, w in edges:
        graph[u].append(w)
        graph[w].append(u)

    colors = [-1] * v

    def is_safe(node: int, col: int) -> bool:
        return all(colors[nei] != col for nei in graph[node])

    def backtrack(node: int) -> bool:
        if node == v:
            return True
        for col in range(m):
            if is_safe(node, col):
                colors[node] = col
                if backtrack(node + 1):
                    return True
                colors[node] = -1
        return False

    return backtrack(0)


if __name__ == "__main__":
    print(find_circle_num([[1, 1, 0], [1, 1, 0], [0, 0, 1]]))  # 2
    print(check_if_prerequisite(2, [[1, 0]], [[0, 1], [1, 0]]))  # [False, True]
    print(graph_coloring(4, [[0, 1], [1, 2], [2, 3], [3, 0]], 2))  # True

Dp Patterns

# PATTERN NAME: DP - Dynamic Programming

# DIFFICULTY: Hard | FREQUENCY: Very High (broad DP family at Google/Meta/Amazon/Microsoft)

# WHEN TO USE:
# - Problems that can be broken down into overlapping subproblems.
# - Optimal substructure property.
# - Problems involving sequences, paths, or combinations.
# - Examples: Fibonacci, Knapsack, Coin Change, Longest Common Subsequence.

# CORE IDEA (INTUITION):
# - Store results of subproblems to avoid redundant calculations.
# - Build up solutions to larger problems using solutions to smaller problems.

# INVARIANTS:
# - Subproblem solutions are reused.
# - Optimal solutions are constructed from optimal subproblem solutions.
# - State representation is crucial (e.g., indices, remaining capacity).

# COMMON MISTAKES:
# - Not identifying overlapping subproblems.
# - Ignoring base cases.
# - Incorrect state representation.
# - Failing to memoize or store subproblem results.
# - Off-by-one errors in indexing.
# - Not considering all possible transitions between states.

# TIME & SPACE:
# - Depends on state space * transition cost; typically O(states * transitions).

# RELATED PROBLEMS:
# - Jump Game II (LC 45)
# - Best Time to Buy and Sell Stock with Cooldown (LC 309)
# - Edit Distance (LC 72)
# - Longest Common Subsequence (LC 1143)
# - Best Time to Buy and Sell Stock III (LC 123)
# - Word Break (LC 139)
# - Palindrome Partitioning II (LC 132)
# - Minimum Edge Reversals (LC 2858) - rerooting DP

from functools import lru_cache


# === Jump Game II ===

# Greedy Optimal - O(n)
def jump_greedy(nums: list[int]) -> int:
    far = end = jumps = 0
    for i in range(len(nums) - 1):
        far = max(far, i + nums[i])
        if i == end:
            jumps += 1
            end = far
    return jumps


# Top-Down DP (Memoization) - O(n^2) worst
def jump_memo(nums: list[int]) -> int:
    n = len(nums)

    @lru_cache(maxsize=None)
    def dfs(i: int) -> int:
        if i >= n - 1:
            return 0
        min_jumps = float("inf")
        for step in range(1, nums[i] + 1):
            if i + step < n:
                min_jumps = min(min_jumps, 1 + dfs(i + step))
        return min_jumps

    return dfs(0)


# Bottom-Up - O(n^2) worst
def jump_bottom_up(nums: list[int]) -> int:
    n = len(nums)
    dp = [float("inf")] * n
    dp[n - 1] = 0
    for i in range(n - 2, -1, -1):
        for step in range(1, nums[i] + 1):
            if i + step < n:
                dp[i] = min(dp[i], 1 + dp[i + step])
    return int(dp[0])


# === Best Time to Buy and Sell Stock with Cooldown ===
# State: (day, can_buy). Selling forces a cooldown (skip the next day).
def max_profit_cooldown(prices: list[int]) -> int:
    n = len(prices)

    @lru_cache(maxsize=None)
    def dfs(day: int, can_buy: int) -> int:
        if day >= n:
            return 0
        if can_buy:
            buy = dfs(day + 1, 0) - prices[day]
            skip = dfs(day + 1, 1)
            return max(buy, skip)
        sell = dfs(day + 2, 1) + prices[day]  # cooldown: jump 2 days
        hold = dfs(day + 1, 0)
        return max(sell, hold)

    return dfs(0, 1)


# === Edit Distance (Bottom-Up) ===
def min_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]


# === Best Time to Buy and Sell Stock III (at most 2 transactions) ===
def max_profit_two_transactions(prices: list[int]) -> int:
    n = len(prices)

    @lru_cache(maxsize=None)
    def dfs(day: int, holding: int, transactions_left: int) -> int:
        if day == n or transactions_left == 0:
            return 0
        if holding == 0:  # can buy
            return max(
                -prices[day] + dfs(day + 1, 1, transactions_left),
                dfs(day + 1, 0, transactions_left),
            )
        return max(  # can sell
            prices[day] + dfs(day + 1, 0, transactions_left - 1),
            dfs(day + 1, 1, transactions_left),
        )

    return dfs(0, 0, 2)


# === Word Break (Bottom-Up) ===
def word_break(s: str, word_dict: list[str]) -> bool:
    dp = [False] * (len(s) + 1)
    dp[0] = True
    words = set(word_dict)
    for i in range(len(s)):
        if not dp[i]:
            continue
        for j in range(i, len(s)):
            if s[i:j + 1] in words:
                dp[j + 1] = True
    return dp[len(s)]


# === Palindrome Partitioning II (minimum cuts) ===
def min_cut(s: str) -> int:
    n = len(s)
    if n <= 1:
        return 0

    pal = [[False] * n for _ in range(n)]
    for i in range(n):        # end index
        for j in range(i + 1):  # start index
            if s[i] == s[j] and (i - j <= 2 or pal[j + 1][i - 1]):
                pal[j][i] = True

    @lru_cache(maxsize=None)
    def get_min_cuts(i: int) -> int:
        if i == n:
            return 0
        best = float("inf")
        for j in range(i, n):
            if pal[i][j]:
                best = min(best, 1 + get_min_cuts(j + 1))
        return best

    return get_min_cuts(0) - 1  # cuts = partitions - 1


# === Rerooting DP: Minimum Edge Reversals ===
def min_edge_reversals(n: int, edges: list[list[int]]) -> list[int]:
    graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append((v, 0))  # forward edge (cost 0)
        graph[v].append((u, 1))  # backward edge (cost 1)

    dp = [0] * n

    def calculate_root(node: int, parent: int) -> int:
        reversals = 0
        for nei, cost in graph[node]:
            if nei == parent:
                continue
            reversals += cost + calculate_root(nei, node)
        return reversals

    def reroot(node: int, parent: int) -> None:
        for nei, cost in graph[node]:
            if nei == parent:
                continue
            dp[nei] = dp[node] + (1 if cost == 0 else -1)
            reroot(nei, node)

    dp[0] = calculate_root(0, -1)
    reroot(0, -1)
    return dp


if __name__ == "__main__":
    print(jump_greedy([2, 3, 1, 1, 4]))       # 2
    print(jump_memo([2, 3, 1, 1, 4]))         # 2
    print(jump_bottom_up([2, 3, 1, 1, 4]))    # 2
    print(max_profit_cooldown([1, 2, 3, 0, 2]))  # 3
    print(min_distance("horse", "ros"))       # 3
    print(max_profit_two_transactions([3, 3, 5, 0, 0, 3, 1, 4]))  # 6
    print(word_break("leetcode", ["leet", "code"]))  # True
    print(min_cut("aab"))                     # 1
    print(min_edge_reversals(6, [[2, 0], [2, 1], [1, 3], [3, 4], [0, 5]]))  # [1, 1, 0, 2, 3, 2]

Greedy

# PATTERN NAME: Greedy
# DIFFICULTY: Medium | FREQUENCY: Very High (intervals, jump game, scheduling at all companies)

# WHEN TO USE:
# - When a locally optimal choice at each step leads to a globally optimal solution.
# - Interval scheduling (merge, meeting rooms, non-overlapping).
# - Activity selection, job sequencing, Jump Game variants.
# - Huffman coding, fractional knapsack.
# - When you can prove the greedy-choice property holds.

# CORE IDEA (INTUITION):
# - At each step make the choice that looks best right now; never reconsider (no backtracking).
# - Works when: greedy-choice property + optimal substructure.
# - Key question: "Can I prove that being greedy never hurts?"

# INVARIANTS:
# - The greedy choice is always part of some optimal solution.
# - After a greedy choice, the remaining problem is a smaller instance of the same problem.
# - Sorting is often a prerequisite.

# COMMON MISTAKES:
# - Applying greedy without proving the greedy-choice property.
# - Sorting by the wrong key (start vs end time matters).
# - Not considering edge cases (empty input, single element).
# - For intervals: sort by START for merge, by END for selection/removal.

# TIME & SPACE:
# - Most greedy: O(n log n) due to sorting, O(1) extra space.
# - Meeting Rooms II: O(n log n) time, O(n) space.
# - Task Scheduler: O(n) time, O(1) space (26 letters).

# RELATED PROBLEMS:
# - Merge Intervals (LC 56)
# - Non-overlapping Intervals (LC 435)
# - Meeting Rooms II (LC 253)
# - Jump Game (LC 55) / Jump Game II (LC 45)
# - Task Scheduler (LC 621)
# - Gas Station (LC 134)
# - Partition Labels (LC 763)

from collections import Counter


# === INTERVAL SCHEDULING ===

# Merge Intervals - sort by start, merge overlapping
def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for i in range(1, len(intervals)):
        last = merged[-1]
        if intervals[i][0] <= last[1]:
            last[1] = max(last[1], intervals[i][1])
        else:
            merged.append(intervals[i])

    return merged


# Insert Interval
def insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    i = 0

    # intervals ending before new_interval starts
    while i < len(intervals) and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

    # merge overlapping intervals with new_interval
    while i < len(intervals) and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    result.append(new_interval)

    # remaining intervals
    while i < len(intervals):
        result.append(intervals[i])
        i += 1

    return result


# Non-overlapping Intervals (minimum removals) - sort by END time
def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])
    removals = 0
    prev_end = float("-inf")

    for start, end in intervals:
        if start >= prev_end:
            prev_end = end  # keep this interval
        else:
            removals += 1   # remove (overlaps)

    return removals


# Meeting Rooms II (minimum rooms) - sweep two sorted arrays
def min_meeting_rooms(intervals: list[list[int]]) -> int:
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)

    rooms = max_rooms = 0
    s = e = 0

    while s < len(starts):
        if starts[s] < ends[e]:
            rooms += 1
            s += 1
        else:
            rooms -= 1
            e += 1
        max_rooms = max(max_rooms, rooms)

    return max_rooms


# === JUMP GAME ===

# Jump Game I - can you reach the last index?
def can_jump(nums: list[int]) -> bool:
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
    return True


# Jump Game II - minimum jumps to reach the end
def jump(nums: list[int]) -> int:
    jumps = cur_end = farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:
            jumps += 1
            cur_end = farthest

    return jumps


# === TASK SCHEDULING ===

# Task Scheduler - minimum intervals with cooldown n
def least_interval(tasks: list[str], n: int) -> int:
    freq = Counter(tasks)
    max_freq = max(freq.values())
    max_count = sum(1 for f in freq.values() if f == max_freq)

    # (max_freq - 1) groups of (n + 1) slots + a final group of max_count tasks
    return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)


# === GAS STATION ===
def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    total_surplus = current_surplus = start = 0

    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total_surplus += diff
        current_surplus += diff
        if current_surplus < 0:
            start = i + 1
            current_surplus = 0

    return start if total_surplus >= 0 else -1


if __name__ == "__main__":
    print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))  # [[1, 6], [8, 10], [15, 18]]
    print(erase_overlap_intervals([[1, 2], [2, 3], [3, 4], [1, 3]]))  # 1
    print(can_jump([2, 3, 1, 1, 4]))    # True
    print(can_jump([3, 2, 1, 0, 4]))    # False
    print(jump([2, 3, 1, 1, 4]))        # 2
    print(least_interval(["A", "A", "A", "B", "B", "B"], 2))  # 8
    print(can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))  # 3

Heap Patterns

# PATTERN NAME: Heap / Priority Queue Patterns
# DIFFICULTY: Medium | FREQUENCY: Very High (Top-K, merge-K, running median at Google/Meta/Amazon)

# WHEN TO USE:
# - Top K / Kth largest or smallest element.
# - Merge K sorted lists/arrays.
# - Running median (two heaps).
# - Scheduling problems (tasks with deadlines/priorities).
# - Any problem needing repeated access to the min or max element.

# CORE IDEA (INTUITION):
# - A heap gives O(log n) insert and O(1) access to the min/max.
# - For "Top K largest": use a MIN-heap of size k (evict the smallest when full).
# - For "Top K smallest": use a MAX-heap of size k (evict the largest when full).
# - For "Merge K sorted": push the first element of each list, pop then push its successor.

# INVARIANTS:
# - Heap size is kept at k for Top-K problems.
# - For the two-heap median: len(lo) >= len(hi), differ by at most 1.

# NOTE: Python's heapq is a MIN-heap. For a max-heap, negate values (push -x). This file uses heapq
# directly (idiomatic) rather than the explicit heap classes in DSA/data-structures/heap/.

# COMMON MISTAKES:
# - Using a max-heap where a min-heap is needed for Top-K (for K largest, use a MIN-heap of size k).
# - Forgetting to seed the merge-K heap with the first element of each list.
# - Not rebalancing the two heaps after every insertion in the median finder.
# - Pushing non-comparable objects; push a (key, item) tuple instead.

# TIME & SPACE:
# - Top K Frequent / Kth Largest / K Closest: O(n log k) time, O(k) space.
# - Merge K Sorted: O(N log k) time, O(k) space.
# - Running Median: O(log n) per add, O(n) space.
# - Reorganize String: ~O(n) time, O(26) space.

# RELATED PROBLEMS:
# - Top K Frequent Elements (LC 347)
# - Kth Largest Element (LC 215)
# - Merge K Sorted Lists (LC 23)
# - K Closest Points to Origin (LC 973)
# - Find Median from Data Stream (LC 295)
# - Reorganize String (LC 767)
# - Last Stone Weight (LC 1046)

import heapq
from collections import Counter


# === KTH LARGEST ELEMENT ===
# Min-heap of size k: the root is always the kth largest seen so far.
def find_kth_largest(nums: list[int], k: int) -> int:
    heap: list[int] = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]


# === TOP K FREQUENT ELEMENTS ===
# Min-heap ordered by frequency; keep the k most frequent.
def top_k_frequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    heap: list[tuple[int, int]] = []  # (count, num)
    for num, count in freq.items():
        heapq.heappush(heap, (count, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for _, num in heap]


# === MERGE K SORTED LISTS ===
# Push (value, list_index, element_index); always pop the global minimum.
def merge_k_lists(lists: list[list[int]]) -> list[int]:
    heap: list[tuple[int, int, int]] = []
    result: list[int] = []

    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    while heap:
        val, li, ei = heapq.heappop(heap)
        result.append(val)
        if ei + 1 < len(lists[li]):
            heapq.heappush(heap, (lists[li][ei + 1], li, ei + 1))

    return result


# === K CLOSEST POINTS TO ORIGIN ===
# Max-heap of size k on distance (negate distance); evict the farthest.
def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
    def dist(p: list[int]) -> int:
        return p[0] * p[0] + p[1] * p[1]

    heap: list[tuple[int, list[int]]] = []  # (-distance, point)
    for p in points:
        heapq.heappush(heap, (-dist(p), p))
        if len(heap) > k:
            heapq.heappop(heap)
    return [p for _, p in heap]


# === RUNNING MEDIAN (two heaps) ===
class MedianFinder:
    def __init__(self) -> None:
        self.lo: list[int] = []  # max-heap (store negatives): smaller half
        self.hi: list[int] = []  # min-heap: larger half

    def add_num(self, num: int) -> None:
        heapq.heappush(self.lo, -num)
        # Ensure max(lo) <= min(hi)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        # Rebalance: lo may have at most 1 more element than hi
        if len(self.lo) < len(self.hi):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def find_median(self) -> float:
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2


# === REORGANIZE STRING ===
# Max-heap by frequency: always place the two most frequent remaining chars.
def reorganize_string(s: str) -> str:
    freq = Counter(s)
    if max(freq.values()) > (len(s) + 1) // 2:
        return ""

    heap: list[tuple[int, str]] = [(-count, ch) for ch, count in freq.items()]
    heapq.heapify(heap)

    result: list[str] = []
    while len(heap) > 1:
        count1, c1 = heapq.heappop(heap)
        count2, c2 = heapq.heappop(heap)
        result.append(c1)
        result.append(c2)
        if count1 + 1 < 0:
            heapq.heappush(heap, (count1 + 1, c1))
        if count2 + 1 < 0:
            heapq.heappush(heap, (count2 + 1, c2))

    if heap:
        result.append(heap[0][1])

    return "".join(result)


if __name__ == "__main__":
    print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))       # 5
    print(sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2)))  # [1, 2]
    print(merge_k_lists([[1, 4, 5], [1, 3, 4], [2, 6]]))  # [1, 1, 2, 3, 4, 4, 5, 6]
    print(k_closest([[1, 3], [-2, 2], [5, 8], [0, 1]], 2))  # closest 2 points

    mf = MedianFinder()
    mf.add_num(1)
    mf.add_num(2)
    print(mf.find_median())  # 1.5
    mf.add_num(3)
    print(mf.find_median())  # 2

    print(reorganize_string("aab"))   # e.g. "aba"
    print(reorganize_string("aaab"))  # ""

Intervals

# PATTERN NAME: Interval Problems
# DIFFICULTY: Medium | FREQUENCY: Very High (merge/insert/meeting-rooms at Google/Meta/Amazon)

# WHEN TO USE:
# - Merge overlapping intervals.
# - Find conflicts/overlaps between intervals.
# - Insert a new interval into a sorted list.
# - Minimum resources for overlapping tasks (meeting rooms).
# - Sweep-line problems.

# CORE IDEA (INTUITION):
# - Sort intervals (usually by start, sometimes by end).
# - Process left-to-right, tracking the "active" state.
# - [a, b] and [c, d] overlap iff a <= d AND c <= b.
# - For minimum resources: sweep line (separate starts and ends).

# INVARIANTS:
# - After sorting by start: if current.start > prev.end, there's no overlap.
# - Sweep line: active count = starts seen - ends seen.
# - For selection problems: sort by END time (greedy).

# COMMON MISTAKES:
# - Sorting by start when you should sort by end (selection vs merge).
# - Off-by-one on touching intervals ([1,2] vs [2,3]) - depends on the problem.
# - Not handling empty input.
# - Forgetting to take max when extending a merged interval's end.
# - Sweep line: ends should process before starts at the same time.

# TIME & SPACE:
# - All interval problems: O(n log n) time (sorting), O(n) space.

# RELATED PROBLEMS:
# - Merge Intervals (LC 56)
# - Insert Interval (LC 57)
# - Non-overlapping Intervals (LC 435)
# - Meeting Rooms (LC 252) / Meeting Rooms II (LC 253)
# - Interval List Intersections (LC 986)
# - Minimum Number of Arrows to Burst Balloons (LC 452)


# Merge Intervals
def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    result = [intervals[0]]

    for i in range(1, len(intervals)):
        last = result[-1]
        if intervals[i][0] <= last[1]:
            last[1] = max(last[1], intervals[i][1])
        else:
            result.append(intervals[i])

    return result


# Insert Interval into a sorted, non-overlapping list
def insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    i = 0

    while i < len(intervals) and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

    while i < len(intervals) and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    result.append(new_interval)

    while i < len(intervals):
        result.append(intervals[i])
        i += 1

    return result


# Interval Intersection (two sorted lists)
def interval_intersection(first_list: list[list[int]], second_list: list[list[int]]) -> list[list[int]]:
    result: list[list[int]] = []
    i = j = 0

    while i < len(first_list) and j < len(second_list):
        lo = max(first_list[i][0], second_list[j][0])
        hi = min(first_list[i][1], second_list[j][1])

        if lo <= hi:
            result.append([lo, hi])

        # advance the one that ends first
        if first_list[i][1] < second_list[j][1]:
            i += 1
        else:
            j += 1

    return result


# Meeting Rooms - can attend all meetings (no overlaps)?
def can_attend_meetings(intervals: list[list[int]]) -> bool:
    intervals.sort(key=lambda x: x[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False
    return True


# Meeting Rooms II - minimum rooms needed (sweep line)
def min_meeting_rooms(intervals: list[list[int]]) -> int:
    events: list[tuple[int, int]] = []
    for start, end in intervals:
        events.append((start, 1))   # meeting starts
        events.append((end, -1))    # meeting ends

    # sort by time; on a tie, end (-1) before start (+1)
    events.sort(key=lambda e: (e[0], e[1]))

    rooms = max_rooms = 0
    for _, delta in events:
        rooms += delta
        max_rooms = max(max_rooms, rooms)

    return max_rooms


# Minimum Number of Arrows to Burst Balloons - sort by end, shoot at earliest end
def find_min_arrow_shots(points: list[list[int]]) -> int:
    points.sort(key=lambda x: x[1])
    arrows = 1
    prev_end = points[0][1]

    for i in range(1, len(points)):
        if points[i][0] > prev_end:
            arrows += 1
            prev_end = points[i][1]

    return arrows


if __name__ == "__main__":
    print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))  # [[1, 6], [8, 10], [15, 18]]
    print(insert([[1, 3], [6, 9]], [2, 5]))            # [[1, 5], [6, 9]]
    print(interval_intersection([[0, 2], [5, 10]], [[1, 5], [8, 12]]))  # [[1, 2], [5, 5], [8, 10]]
    print(can_attend_meetings([[0, 30], [5, 10], [15, 20]]))  # False
    print(min_meeting_rooms([[0, 30], [5, 10], [15, 20]]))    # 2
    print(find_min_arrow_shots([[10, 16], [2, 8], [1, 6], [7, 12]]))  # 2

K Sum Reduction

# PATTERN NAME: k-Sum Reduction (Recursive Two Pointer)
# DIFFICULTY: Medium | FREQUENCY: High (generalizes 2Sum/3Sum/4Sum at Google/Meta/Amazon)

# INTUITION:
# - Reduce a k-Sum problem to 2-Sum by recursively fixing elements.
# - Use the two-pointer technique for the base case (2-Sum).
# - Sort the array to enable two pointers and easy duplicate skipping.

# ALGORITHM:
# 1. Sort the array.
# 2. Recursively reduce k-Sum to (k-1)-Sum by fixing one element at a time.
# 3. Base case (k == 2): two pointers from both ends, moving based on the sum vs target.
# 4. Skip duplicates to avoid duplicate tuples.

# TIME COMPLEXITY: O(n^(k-1))  (4-Sum: O(n^3); sorting O(n log n); recursion depth k-2)
# SPACE COMPLEXITY: O(k) for recursion depth + current tuple.

# KEY TECHNIQUES: reduction, two pointers, duplicate skipping, tightened loop bound (len - k + 1).
# GENERALIZABLE: works for any k-Sum - just change the initial call k_sum(0, k, [], 0).

# COMMON MISTAKES:
# - Forgetting to sort before applying two pointers / duplicate skipping.
# - Not skipping duplicate starting elements (i > start and nums[i] == nums[i-1]).
# - Not skipping duplicates on both ends after recording a match.

# RELATED PROBLEMS:
# - Two Sum II (LC 167)
# - 3Sum (LC 15)
# - 4Sum (LC 18)


def four_sum(nums: list[int], target: int) -> list[list[int]]:
    quads: list[list[int]] = []
    nums.sort()

    def k_sum(start: int, k: int, cur_arr: list[int], cur_sum: int) -> None:
        if k <= 2:
            i, j = start, len(nums) - 1
            while i < j:
                total = nums[i] + nums[j] + cur_sum
                if total == target:
                    quads.append([*cur_arr, nums[i], nums[j]])
                    while i < j and nums[i] == nums[i + 1]:
                        i += 1
                    while i < j and nums[j] == nums[j - 1]:
                        j -= 1
                    i += 1
                    j -= 1
                elif total < target:
                    i += 1
                else:
                    j -= 1
        else:
            for i in range(start, len(nums) - k + 1):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                cur_arr.append(nums[i])
                k_sum(i + 1, k - 1, cur_arr, cur_sum + nums[i])
                cur_arr.pop()

    k_sum(0, 4, [], 0)
    return quads


if __name__ == "__main__":
    # [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
    print(four_sum([1, 0, -1, 0, -2, 2], 0))

Matrix

# PATTERN NAME: Matrix / Grid Patterns
# DIFFICULTY: Medium | FREQUENCY: Very High (islands, spiral, rotate, 2D search at all companies)

# WHEN TO USE:
# - 2D grid traversal (islands, shortest path).
# - Matrix rotation, spiral order.
# - Search in a sorted 2D matrix.
# - Flood fill, connected components in a grid.

# CORE IDEA (INTUITION):
# - Grids are implicit graphs - each cell connects to its neighbors.
# - Use DFS/BFS for traversal, a visited marker to avoid revisiting.
# - For sorted matrices: treat as a flattened sorted array or use staircase search.
# - Direction arrays simplify neighbor iteration.

# INVARIANTS:
# - Always check bounds: 0 <= row < m, 0 <= col < n.
# - Mark visited BEFORE enqueuing (BFS) to avoid duplicates.
# - 4-directional array: [(0,1),(0,-1),(1,0),(-1,0)].

# COMMON MISTAKES:
# - Forgetting bounds checks before accessing grid[r][c].
# - Marking visited AFTER enqueuing (causes duplicates in BFS).
# - Wrong direction array (4- vs 8-directional).
# - Spiral order: not re-checking top <= bottom and left <= right after each direction.

# TIME & SPACE:
# - Grid DFS/BFS: O(m*n) time, O(m*n) space.
# - Spiral / Rotate / Set Zeroes: O(m*n) time, O(1) extra space.
# - Staircase search: O(m + n) time, O(1) space.

# RELATED PROBLEMS:
# - Number of Islands (LC 200)
# - Spiral Matrix (LC 54)
# - Rotate Image (LC 48)
# - Search a 2D Matrix II (LC 240)
# - Set Matrix Zeroes (LC 73)
# - Word Search (LC 79)


# === DIRECTION HELPERS ===
DIRS_4 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
DIRS_8 = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]


def in_bounds(r: int, c: int, m: int, n: int) -> bool:
    return 0 <= r < m and 0 <= c < n


# === NUMBER OF ISLANDS (DFS on grid) ===
def num_islands(grid: list[list[str]]) -> int:
    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(r: int, c: int) -> None:
        if not in_bounds(r, c, m, n) or grid[r][c] == "0":
            return
        grid[r][c] = "0"  # mark visited by sinking
        for dr, dc in DIRS_4:
            dfs(r + dr, c + dc)

    for r in range(m):
        for c in range(n):
            if grid[r][c] == "1":
                dfs(r, c)
                count += 1

    return count


# === SPIRAL ORDER ===
def spiral_order(matrix: list[list[int]]) -> list[int]:
    result: list[int] = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        top += 1

        for r in range(top, bottom + 1):
            result.append(matrix[r][right])
        right -= 1

        if top <= bottom:
            for c in range(right, left - 1, -1):
                result.append(matrix[bottom][c])
            bottom -= 1

        if left <= right:
            for r in range(bottom, top - 1, -1):
                result.append(matrix[r][left])
            left += 1

    return result


# === ROTATE MATRIX 90 DEGREES CLOCKWISE (in-place) ===
# Step 1: transpose. Step 2: reverse each row.
def rotate(matrix: list[list[int]]) -> list[list[int]]:
    n = len(matrix)

    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    for row in matrix:
        row.reverse()

    return matrix


# === SEARCH IN SORTED MATRIX (staircase from top-right) ===
def search_matrix(matrix: list[list[int]], target: int) -> bool:
    r, c = 0, len(matrix[0]) - 1

    while r < len(matrix) and c >= 0:
        if matrix[r][c] == target:
            return True
        if matrix[r][c] > target:
            c -= 1
        else:
            r += 1

    return False


# === SET MATRIX ZEROES (O(1) space using first row/col as markers) ===
def set_zeroes(matrix: list[list[int]]) -> list[list[int]]:
    m, n = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][c] == 0 for c in range(n))
    first_col_zero = any(matrix[r][0] == 0 for r in range(m))

    for r in range(1, m):
        for c in range(1, n):
            if matrix[r][c] == 0:
                matrix[r][0] = 0
                matrix[0][c] = 0

    for r in range(1, m):
        for c in range(1, n):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0

    if first_row_zero:
        for c in range(n):
            matrix[0][c] = 0
    if first_col_zero:
        for r in range(m):
            matrix[r][0] = 0

    return matrix


if __name__ == "__main__":
    print(spiral_order([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
    # [1, 2, 3, 6, 9, 8, 7, 4, 5]

    print(rotate([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
    # [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

    print(search_matrix([[1, 4, 7], [2, 5, 8], [3, 6, 9]], 5))   # True
    print(search_matrix([[1, 4, 7], [2, 5, 8], [3, 6, 9]], 10))  # False

Monotonic Queue

# PATTERN NAME: Monotonic Queue (Deque)
# DIFFICULTY: Hard | FREQUENCY: High (sliding window max/min at Google/Amazon)

# WHEN TO USE:
# - Sliding window maximum / minimum.
# - Constrained subsequence sum.
# - Problems needing the max/min of a moving window in O(1) amortized.

# CORE IDEA (INTUITION):
# - Maintain a deque of INDICES whose values are monotonic.
# - For a max-queue: keep values decreasing (front = max of the window).
# - Before adding a new element, pop smaller elements from the back (they can never be the max).
# - Remove front indices that fall outside the window.

# INVARIANTS:
# - Deque values are monotonic (decreasing for max, increasing for min).
# - The front is always the answer (max/min) for the current window.
# - Indices in the deque are within the current window.

# COMMON MISTAKES:
# - Storing values instead of indices (can't tell when they leave the window).
# - Popping from the wrong end (front for window expiry, back for monotonic property).
# - Not removing expired indices from the front.
# - Using a plain list with pop(0) (O(n)) instead of collections.deque.

# TIME & SPACE:
# - Time: O(n) - each element enters and leaves the deque once.
# - Space: O(k) where k is the window size.

# RELATED PROBLEMS:
# - Sliding Window Maximum (LC 239)
# - Constrained Subsequence Sum (LC 1425)
# - Shortest Subarray with Sum at Least K (LC 862)
# - Jump Game VI (LC 1696)

from collections import deque


# Sliding Window Maximum - max of every window of size k
def max_sliding_window(nums: list[int], k: int) -> list[int]:
    result: list[int] = []
    dq: deque[int] = deque()  # indices, values decreasing

    for i in range(len(nums)):
        # remove indices outside the window
        if dq and dq[0] < i - k + 1:
            dq.popleft()

        # remove smaller values from the back (they can't be the max)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        # front is the max of the current window
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result


# Sliding Window Minimum - min of every window of size k
def min_sliding_window(nums: list[int], k: int) -> list[int]:
    result: list[int] = []
    dq: deque[int] = deque()  # indices, values increasing

    for i in range(len(nums)):
        if dq and dq[0] < i - k + 1:
            dq.popleft()

        while dq and nums[dq[-1]] > nums[i]:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result


if __name__ == "__main__":
    print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
    # [3, 3, 5, 5, 6, 7]
    print(min_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
    # [-1, -3, -3, -3, 3, 3]

Monotonic Stack

# PATTERN NAME: Monotonic Stack
# DIFFICULTY: Medium | FREQUENCY: Very High (next-greater-element family at Google/Amazon/Meta)

# WHEN TO USE:
# - Next/previous greater or smaller element.
# - Largest rectangle in a histogram.
# - Stock span, daily temperatures.
# - Problems asking "for each element, find the nearest X".

# CORE IDEA (INTUITION):
# - Maintain a stack whose elements are monotonic (increasing or decreasing).
# - Before pushing, pop all elements that violate the monotonic property.
# - The popped elements have found their "answer" (the current element).
# - Store indices (not values) when you need distances.

# INVARIANTS:
# - Decreasing stack: each element is smaller than the one below it (top is smallest).
# - When we pop, the current element is the "next greater" for the popped element.
# - Each element is pushed and popped at most once -> O(n) total.

# COMMON MISTAKES:
# - Storing values when you need indices (for distances).
# - Wrong monotonic direction (increasing vs decreasing).
# - Forgetting to process remaining stack elements after the loop.
# - Off-by-one in histogram width calculation.

# TIME & SPACE:
# - Time: O(n) - each element pushed/popped once.
# - Space: O(n) for the stack.

# RELATED PROBLEMS:
# - Next Greater Element I (LC 496) / II (LC 503)
# - Daily Temperatures (LC 739)
# - Largest Rectangle in Histogram (LC 84)
# - Trapping Rain Water (LC 42)
# - Remove K Digits (LC 402)
# - Sum of Subarray Minimums (LC 907)


# Daily Temperatures - days until a warmer temperature (decreasing stack of indices)
def daily_temperatures(temperatures: list[int]) -> list[int]:
    result = [0] * len(temperatures)
    stack: list[int] = []  # indices, temperatures decreasing

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_index = stack.pop()
            result[prev_index] = i - prev_index
        stack.append(i)

    return result


# Next Greater Element (circular array)
def next_greater_elements(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack: list[int] = []  # indices

    # iterate twice to simulate the circular array
    for i in range(2 * n):
        idx = i % n
        while stack and nums[stack[-1]] < nums[idx]:
            result[stack.pop()] = nums[idx]
        if i < n:
            stack.append(idx)

    return result


# Largest Rectangle in Histogram
def largest_rectangle_area(heights: list[int]) -> int:
    stack: list[int] = []  # indices, heights increasing
    max_area = 0
    heights = heights + [0]  # sentinel to flush the stack

    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


if __name__ == "__main__":
    print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
    # [1, 1, 4, 2, 1, 1, 0, 0]
    print(next_greater_elements([1, 2, 1]))    # [2, -1, 2]
    print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))  # 10

Prefix Sum Pattern

# PATTERN NAME: Prefix Sum
# DIFFICULTY: Medium | FREQUENCY: Very High (subarray-sum problems at Google/Meta/Amazon)

# WHEN TO USE:
# - Calculating the sum of subarrays multiple times.
# - Counting subarrays that meet a certain sum condition.
# - Optimizing brute-force solutions with nested sum loops.

# CORE IDEA (INTUITION):
# - Precompute cumulative sums so any subarray sum is a constant-time difference.
# - Use a hash map of prefix-sum frequencies to count subarrays with a specific property.
# - Key identity: sum(i..j) == prefix[j] - prefix[i-1]; a subarray sums to k when a previous
#   prefix equals current_sum - k.

# COMMON MISTAKES:
# - Not seeding the prefix-sum map with the base case {0: 1}.
# - Updating the map before checking (double counts the current element).
# - Misunderstanding the relationship between current sum, target, and previous sums.

# TIME & SPACE:
# - Time: O(n).
# - Space: O(n) for the prefix-sum hash map.

# RELATED PROBLEMS:
# - Subarray Sum Equals K (LC 560)
# - Continuous Subarray Sum (LC 523)
# - Count of Range Sum (LC 327)
# - Contiguous Array (LC 525)
# - Subarray Sums Divisible by K (LC 974)


# Problem: Subarray Sum Equals K
# Count the continuous subarrays whose sum equals k.
def subarray_sum(nums: list[int], k: int) -> int:
    count = 0
    prefix_freq: dict[int, int] = {0: 1}
    total = 0

    for n in nums:
        total += n
        if total - k in prefix_freq:
            count += prefix_freq[total - k]
        prefix_freq[total] = prefix_freq.get(total, 0) + 1

    return count


if __name__ == "__main__":
    print(subarray_sum([1, 1, 1], 2))        # 2
    print(subarray_sum([1, 2, 3], 3))        # 2
    print(subarray_sum([3, 4, 7, 2, -3, 1, 4, 2], 7))  # 4

Sliding Window

# PATTERN NAME: Sliding Window
# DIFFICULTY: Medium | FREQUENCY: Very High (arrays/strings staple at Google/Meta/Amazon)

# WHEN TO USE:
# - When you need to find a contiguous subarray or substring that satisfies certain conditions.
# - When you need to optimize a brute-force solution that involves nested loops over a linear data structure.
# - When you need to maintain a running total or count of elements in a dynamic window.

# CORE IDEA (INTUITION):
# - Use two pointers to represent the boundaries of the window.
# - Expand and contract the window based on the problem's requirements.
# - Maintain necessary data structures (like dicts or counters) to track elements within the window.

# TEMPLATE / SKELETON:

# Problem: Longest Repeating Character Replacement
# Given a string s that consists of only uppercase English letters, you can perform at most k operations
# on that string. In one operation, you can choose any character of the string and change it to any other
# uppercase English character.


def character_replacement(s: str, k: int) -> int:
    freq: dict[str, int] = {}
    left = 0
    max_len = 0
    max_freq = 0

    for right in range(len(s)):
        char = s[right]
        freq[char] = freq.get(char, 0) + 1
        max_freq = max(max_freq, freq[char])

        # window size - max_freq > k
        while (right - left + 1) - max_freq > k:
            char_to_remove = s[left]
            freq[char_to_remove] -= 1
            if freq[char_to_remove] == 0:
                del freq[char_to_remove]
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len


# COMMON MISTAKES:
# - Not updating the window boundaries correctly.
# - Forgetting to maintain necessary data structures for tracking elements within the window.
# - Not handling edge cases, such as empty strings or arrays.

# TIME & SPACE:
# - Time Complexity: O(n), where n is the length of the input string or array.
# - Space Complexity: O(1) or O(k), depending on the number of unique elements in the window.

# RELATED PROBLEMS:
# - Minimum Size Subarray Sum
# - Longest Substring Without Repeating Characters
# - Permutation in String
# - Find All Anagrams in a String
# - Sliding Window Maximum
# - Subarrays with K Different Integers
# - Longest Substring with At Most K Distinct Characters


# Problem: Binary Subarrays With Sum
# Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.
# A subarray is a contiguous part of the array.

# Intuition:
# - We can use the sliding window technique to count the number of subarrays with at most a certain sum.
# - By calculating the number of subarrays with at most 'goal' and subtracting the number of subarrays
#   with at most 'goal - 1', we get the number of subarrays with exactly 'goal' sum.
# - This approach reduces the space complexity compared to using a hashmap to store prefix sums.


def num_subarrays_with_sum(nums: list[int], goal: int) -> int:
    # Can be solved like "subarrays with sum k" (hashmap approach) but that takes O(n) space.
    # Reduce the space:
    #   no. of subarrays with exact sum goal =
    #       (no. of subarrays with at most sum goal)
    #       - (no. of subarrays with at most sum goal - 1)

    def at_most(g: int) -> int:
        if g < 0:
            return 0
        left = 0
        count = 0
        window_sum = 0
        for right in range(len(nums)):
            window_sum += nums[right]
            while window_sum > g:
                window_sum -= nums[left]
                left += 1
            count += right - left + 1
        return count

    return at_most(goal) - at_most(goal - 1)


# Problem: Subarrays with K Different Integers
# Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good
# if the number of different integers in that subarray is exactly K.
# Return the number of good subarrays of A.

# Intuition:
# - Similar to the previous problem, use the sliding window technique to count the number of subarrays
#   with at most K distinct integers.
# - subarrays with exactly K = at_most(K) - at_most(K - 1)


def subarrays_with_k_distinct(nums: list[int], k: int) -> int:
    def at_most(kk: int) -> int:
        if kk < 0:
            return 0
        left = 0
        freq: dict[int, int] = {}
        count = 0
        for right in range(len(nums)):
            freq[nums[right]] = freq.get(nums[right], 0) + 1
            while len(freq) > kk:
                freq[nums[left]] -= 1
                if freq[nums[left]] == 0:
                    del freq[nums[left]]
                left += 1
            count += right - left + 1
        return count

    return at_most(k) - at_most(k - 1)


# Examples (only run when executed directly)
if __name__ == "__main__":
    print(character_replacement("AABABBA", 1))  # 4
    print(num_subarrays_with_sum([1, 0, 1, 0, 1], 2))  # 4
    print(subarrays_with_k_distinct([1, 2, 1, 2, 3], 2))  # 7

Suffix Trie

# PATTERN NAME: Suffix Trie for Counting Distinct Substrings
# DIFFICULTY: Hard | FREQUENCY: Medium (distinct-substring / suffix-structure problems at Google)

# PROBLEM STATEMENT: Given a string s, count the number of distinct substrings of s.

# WHEN TO USE:
# - Count distinct substrings in a string.
# - Efficiently store and query all suffixes of a string.
# - String processing, pattern matching, substring queries.

# CORE IDEA (INTUITION):
# - A suffix trie stores all suffixes; each root-to-node path is a distinct substring.
# - The number of distinct substrings = number of trie nodes (excluding the root).
# - A suffix array + LCP array counts distinct substrings more efficiently.

# INVARIANTS:
# - Each trie node represents a unique substring.
# - Distinct substrings = node count (excluding the root).
# - Suffix-array approach: sum over suffixes of (length - LCP with the previous suffix).

# COMMON MISTAKES:
# - Counting the empty substring when the problem excludes it.
# - Overcounting duplicate substrings.
# - Using brute force on large inputs (TLE).
# - Missing some suffixes when building the trie/array.

# TIME & SPACE:
# - Brute force: O(n^3) time, O(n^2) space.
# - Suffix Trie: O(n^2) time and space.
# - Suffix Array + LCP: O(n^2 log n) here (simple comparator); O(n) extra space.

# RELATED PROBLEMS:
# - Longest Repeating Substring
# - Longest Common Substring of Two Strings
# - Distinct Echo Substrings (LC 1316)


def count_subs(s: str) -> int:
    # return brute_force(s)
    # return suffix_trie(s)
    return suffix_array_lcp(s)


def brute_force(s: str) -> int:
    # Time: O(n^3), Space: O(n^2)
    seen: set[str] = set()
    n = len(s)
    for i in range(n):
        cur = ""
        for j in range(i, n):
            cur += s[j]
            seen.add(cur)
    return len(seen)


def suffix_trie(s: str) -> int:
    # Time: O(n^2), Space: O(n^2)
    root: dict[str, dict] = {}
    count = 0

    for i in range(len(s)):
        node = root
        for j in range(i, len(s)):
            ch = s[j]
            if ch not in node:
                node[ch] = {}
                count += 1  # a new node = a new distinct substring
            node = node[ch]

    return count


def suffix_array_lcp(s: str) -> int:
    # Build a suffix array (by starting index), then sum (length - LCP with previous suffix).
    n = len(s)
    if n == 0:
        return 0

    suffixes = sorted(range(n), key=lambda i: s[i:])

    def lcp(i: int, j: int) -> int:
        length = 0
        while i < n and j < n and s[i] == s[j]:
            length += 1
            i += 1
            j += 1
        return length

    result = n - suffixes[0]  # first suffix contributes all its prefixes
    for i in range(1, n):
        cur_len = n - suffixes[i]
        common = lcp(suffixes[i], suffixes[i - 1])
        result += cur_len - common

    return result


if __name__ == "__main__":
    print(count_subs("abc"))  # 6 (a, b, c, ab, bc, abc)
    print(count_subs("aaa"))  # 3 (a, aa, aaa)

Tree Patterns

# PATTERN NAME: Binary Tree Patterns
# DIFFICULTY: Medium | FREQUENCY: Very High (depth, diameter, LCA, path sum at all companies)

# WHEN TO USE:
# - Any problem involving binary trees (not just BSTs).
# - Depth, diameter, path sum, LCA, invert, serialize.
# - Most tree problems are naturally recursive: solve subtrees, combine at the root.

# CORE IDEA (INTUITION):
# - Trees are recursive: every subtree is itself a tree.
# - Most solutions follow: process left, process right, combine at the current node.
# - Two approaches: top-down (pass info down) vs bottom-up (return info up).
# - Bottom-up is usually cleaner.

# INVARIANTS:
# - Base case: a null node returns a neutral value (0, -inf, None, True).
# - Each node visited once -> O(n) time.
# - Recursion depth = tree height -> O(h) space, worst case O(n) for skewed trees.

# COMMON MISTAKES:
# - Forgetting the base case (null node).
# - Confusing top-down vs bottom-up (diameter / max path sum MUST be bottom-up).
# - In max path sum: forgetting to clamp negative paths to 0.
# - In LCA: not handling the case where p or q IS the root.
# - In serialize: not handling null markers during deserialize.

# TIME & SPACE:
# - All recursive traversals: O(n) time, O(h) space (O(n) worst case).
# - BFS (right side view): O(n) time, O(w) space (w = max width).

# RELATED PROBLEMS:
# - Maximum Depth of Binary Tree (LC 104)
# - Invert Binary Tree (LC 226)
# - Diameter of Binary Tree (LC 543)
# - Lowest Common Ancestor (LC 236)
# - Binary Tree Maximum Path Sum (LC 124)
# - Path Sum (LC 112)
# - Same Tree (LC 100)
# - Subtree of Another Tree (LC 572)
# - Serialize and Deserialize Binary Tree (LC 297)
# - Binary Tree Right Side View (LC 199)

from __future__ import annotations
from collections import deque


# Self-contained node (see also DSA/data-structures/tree/bst.py)
class TreeNode:
    def __init__(self, val: int = 0, left: TreeNode | None = None, right: TreeNode | None = None) -> None:
        self.val = val
        self.left = left
        self.right = right


# === MAX DEPTH ===
def max_depth(root: TreeNode | None) -> int:
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))


# === INVERT BINARY TREE ===
def invert_tree(root: TreeNode | None) -> TreeNode | None:
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root


# === DIAMETER OF BINARY TREE ===
# Longest path between any two nodes (may not pass through the root).
def diameter_of_binary_tree(root: TreeNode | None) -> int:
    diameter = 0

    def height(node: TreeNode | None) -> int:
        nonlocal diameter
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        diameter = max(diameter, left + right)  # path through this node
        return 1 + max(left, right)

    height(root)
    return diameter


# === LOWEST COMMON ANCESTOR (general binary tree) ===
def lowest_common_ancestor(root: TreeNode | None, p: TreeNode, q: TreeNode) -> TreeNode | None:
    if not root or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root       # p and q are in different subtrees
    return left or right  # both in the same subtree


# === PATH SUM (root to leaf) ===
def has_path_sum(root: TreeNode | None, target_sum: int) -> bool:
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == target_sum
    return (has_path_sum(root.left, target_sum - root.val)
            or has_path_sum(root.right, target_sum - root.val))


# === MAXIMUM PATH SUM (any node to any node) ===
def max_path_sum(root: TreeNode | None) -> int:
    max_sum = float("-inf")

    def dfs(node: TreeNode | None) -> int:
        nonlocal max_sum
        if not node:
            return 0
        left = max(0, dfs(node.left))   # ignore negative paths
        right = max(0, dfs(node.right))
        max_sum = max(max_sum, left + right + node.val)  # path through this node
        return node.val + max(left, right)               # best single path upward

    dfs(root)
    return int(max_sum)


# === SAME TREE ===
def is_same_tree(p: TreeNode | None, q: TreeNode | None) -> bool:
    if not p and not q:
        return True
    if not p or not q:
        return False
    return p.val == q.val and is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)


# === SUBTREE OF ANOTHER TREE ===
def is_subtree(root: TreeNode | None, sub_root: TreeNode | None) -> bool:
    if not root:
        return False
    if is_same_tree(root, sub_root):
        return True
    return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)


# === SERIALIZE / DESERIALIZE (preorder with null markers) ===
def serialize(root: TreeNode | None) -> str:
    result: list[str] = []

    def dfs(node: TreeNode | None) -> None:
        if not node:
            result.append("null")
            return
        result.append(str(node.val))
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return ",".join(result)


def deserialize(data: str) -> TreeNode | None:
    vals = data.split(",")
    idx = 0

    def dfs() -> TreeNode | None:
        nonlocal idx
        if vals[idx] == "null":
            idx += 1
            return None
        node = TreeNode(int(vals[idx]))
        idx += 1
        node.left = dfs()
        node.right = dfs()
        return node

    return dfs()


# === RIGHT SIDE VIEW (BFS level order, take the last of each level) ===
def right_side_view(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    result: list[int] = []
    queue: deque[TreeNode] = deque([root])

    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.popleft()
            if i == size - 1:
                result.append(node.val)  # rightmost node at this level
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return result


if __name__ == "__main__":
    root = TreeNode(1,
                    TreeNode(2, TreeNode(4), TreeNode(5)),
                    TreeNode(3))

    print(max_depth(root))               # 3
    print(diameter_of_binary_tree(root))  # 3
    print(has_path_sum(root, 7))          # True (1 -> 2 -> 4)
    print(right_side_view(root))          # [1, 3, 5]

    serialized = serialize(root)
    print(serialized)                     # 1,2,4,null,null,5,null,null,3,null,null
    print(max_depth(deserialize(serialized)))  # 3

Two Pointers

# PATTERN NAME: Two Pointers
# DIFFICULTY: Easy | FREQUENCY: Very High (sorted-array / palindrome / partition staple at all companies)

# WHEN TO USE:
# - Sorted array problems (pair sum, triplet sum, remove duplicates)
# - Palindrome checking
# - Merging two sorted arrays
# - Partitioning (Dutch National Flag)
# - Container with most water, trapping rain water

# CORE IDEA (INTUITION):
# - Use two pointers moving toward each other (opposite direction) or in the same direction
#   (fast/slow) to reduce O(n^2) to O(n).
# - Opposite direction: start from both ends, converge based on a condition.
# - Same direction: fast pointer explores, slow pointer tracks the valid position.

# INVARIANTS:
# - Pointers never cross (opposite) or slow never passes fast (same direction).
# - The search space shrinks with each step.
# - For sorted arrays: moving left pointer right increases the sum, moving right pointer left decreases it.

# COMMON MISTAKES:
# - Forgetting to sort the array first (two pointers on unsorted data gives wrong answers).
# - Off-by-one: using left <= right when it should be left < right.
# - Not skipping duplicates in problems like 3Sum.
# - Moving the wrong pointer (always move the one that improves the condition).
# - In Dutch National Flag: incrementing mid after swapping with high.

# TIME & SPACE:
# - Time: O(n) for a single pass, O(n log n) if sorting is needed first.
# - Space: O(1) - in-place pointer manipulation.

# RELATED PROBLEMS:
# - Two Sum II (LC 167)
# - 3Sum (LC 15)
# - Container With Most Water (LC 11)
# - Trapping Rain Water (LC 42)
# - Valid Palindrome (LC 125)
# - Remove Duplicates from Sorted Array (LC 26)
# - Sort Colors (LC 75)
# - Move Zeroes (LC 283)
# - Squares of a Sorted Array (LC 977)


# === OPPOSITE DIRECTION ===

# Two Sum (sorted array)
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1

    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1
        else:
            right -= 1

    return [-1, -1]


# Container With Most Water
def max_area(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)

        # Move the shorter side - it's the bottleneck
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water


# Valid Palindrome (with alphanumeric filter)
def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1

    return True


# === SAME DIRECTION (Fast/Slow) ===

# Remove Duplicates from Sorted Array (in-place)
def remove_duplicates(nums: list[int]) -> int:
    if len(nums) == 0:
        return 0

    slow = 0  # points to the last unique element

    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]

    return slow + 1  # length of the unique portion


# === DUTCH NATIONAL FLAG (3-way partition) ===

# Sort Colors (0s, 1s, 2s)
def sort_colors(nums: list[int]) -> list[int]:
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            # don't increment mid - the swapped element still needs checking

    return nums


if __name__ == "__main__":
    print(two_sum_sorted([2, 7, 11, 15], 9))                    # [0, 1]
    print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))                # 49
    print(is_palindrome("A man, a plan, a canal: Panama"))      # True
    print(remove_duplicates([1, 1, 2, 2, 3]))                   # 3
    print(sort_colors([2, 0, 2, 1, 1, 0]))                      # [0, 0, 1, 1, 2, 2]

Union Find Patterns

# PATTERN NAME: Union-Find (Disjoint Set Union)
# DIFFICULTY: Medium | FREQUENCY: Very High (connectivity, grouping, MST at Google/Amazon/Meta)

# PROBLEM TYPES:
# - Dynamic connectivity problems.
# - Network connectivity, clustering.
# - Connected components (image processing).
# - Kruskal's Minimum Spanning Tree.

# WHEN TO USE:
# - Efficiently manage and merge disjoint sets.
# - Check if two elements are in the same set.
# - Dynamically connect components / track connected components.

# CORE IDEA (INTUITION):
# - Represent each element as a node in a tree; each tree is a set with a root representative.
# - Path compression flattens the tree during find.
# - Union by rank/size keeps trees shallow.

# INVARIANTS:
# - Each element points to its parent; the root points to itself.
# - Rank/size is maintained to optimize unions.
# - Path compression speeds up future finds.

# COMMON OPERATIONS:
# - find(x): representative (root) of x's set.
# - union(x, y): merge the sets of x and y.
# - is_connected(x, y): whether x and y share a root.

# COMMON MISTAKES:
# - Skipping path compression in find.
# - Skipping union by rank/size in union.
# - Forgetting to lazily initialize new elements (this dict-based version does it in find).
# - Assuming all elements are known beforehand.

# TIME & SPACE:
# - Time: O(alpha(N)) per operation (inverse Ackermann - effectively O(1) amortized).
# - Space: O(N) for parent and rank maps.

# RELATED PROBLEMS:
# - Number of Connected Components (LC 323)
# - Redundant Connection (LC 684)
# - Accounts Merge (LC 721)
# - Graph Valid Tree (LC 261)
# - Checking Existence of Edge Length Limited Paths (LC 1697)


# Dict-based Union-Find that lazily initializes unknown elements (handy for sparse/string keys).
class UnionFind:
    def __init__(self) -> None:
        self.parents: dict[int, int] = {}
        self.ranks: dict[int, int] = {}

    def find(self, x: int) -> int:
        if x not in self.parents:
            self.parents[x] = x
            self.ranks[x] = 0

        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])  # path compression
        return self.parents[x]

    def union(self, x: int, y: int) -> bool:
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False  # already united

        if self.ranks[root_x] > self.ranks[root_y]:
            self.parents[root_y] = root_x
        elif self.ranks[root_y] > self.ranks[root_x]:
            self.parents[root_x] = root_y
        else:
            self.parents[root_y] = root_x
            self.ranks[root_x] += 1
        return True

    def is_connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


# EXAMPLE: Checking Existence of Edge Length Limited Paths
# Offline queries: sort queries and edges by limit, union edges under the limit, then answer.
def distance_limited_paths_exist(n: int, edge_list: list[list[int]],
                                 queries: list[list[int]]) -> list[bool]:
    answer = [False] * len(queries)

    # attach the original index so we can restore order after sorting
    indexed_queries = [(*q, i) for i, q in enumerate(queries)]
    indexed_queries.sort(key=lambda q: q[2])
    edge_list.sort(key=lambda e: e[2])

    uf = UnionFind()
    edge_idx = 0

    for p, q, limit, org_idx in indexed_queries:
        while edge_idx < len(edge_list) and limit > edge_list[edge_idx][2]:
            x, y, _ = edge_list[edge_idx]
            uf.union(x, y)
            edge_idx += 1

        if uf.is_connected(p, q):
            answer[org_idx] = True

    return answer


if __name__ == "__main__":
    edge_list = [[0, 2, 4], [1, 2, 3], [2, 3, 1], [4, 5, 5]]
    queries = [[2, 3, 2], [1, 3, 3], [2, 0, 5], [0, 5, 6]]
    print(distance_limited_paths_exist(6, edge_list, queries))
    # [True, False, True, False]