Blind 75 Graphs, Trees, And DP Deep Dive

Invariant: once an original node is in copies, every future edge that reaches that original should reuse the same clone. The common mistake is cloning neighbors before memoizing the current node, which recurses forever on cycles.

def clone_graph(node):
    if node is None:
        return None

    copies = {}

    def dfs(original):
        if original in copies:
            return copies[original]

        clone = Node(original.val)
        copies[original] = clone
        clone.neighbors = [dfs(neighbor) for neighbor in original.neighbors]
        return clone

    return dfs(node)

Reverse the flow. Invariant: a cell reached from an ocean border by moving only to equal-or-higher neighbors can drain back to that ocean in the original direction. Test one row, one column, flat terrain, and a high ridge surrounded by lower cells.

def pacific_atlantic(heights):
    if not heights or not heights[0]:
        return []

    rows, cols = len(heights), len(heights[0])

    def flood(starts):
        seen = set(starts)
        stack = list(starts)
        while stack:
            r, c = stack.pop()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if (
                    0 <= nr < rows
                    and 0 <= nc < cols
                    and (nr, nc) not in seen
                    and heights[nr][nc] >= heights[r][c]
                ):
                    seen.add((nr, nc))
                    stack.append((nr, nc))
        return seen

    pacific = flood([(0, c) for c in range(cols)] + [(r, 0) for r in range(rows)])
    atlantic = flood([(rows - 1, c) for c in range(cols)] + [(r, cols - 1) for r in range(rows)])
    return [[r, c] for r, c in sorted(pacific & atlantic)]

Invariant: the recursive return value is the best one-sided path that can extend to the parent. The global best can use both children through the current node. The common mistake is returning a forked path upward, which is not a valid path for the parent to extend.

def max_path_sum(root):
    best = -10**18

    def one_sided(node):
        nonlocal best
        if node is None:
            return 0

        left = max(0, one_sided(node.left))
        right = max(0, one_sided(node.right))
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    one_sided(root)
    return best

Preorder with null markers is enough because each token stream can be consumed from left to right. Test an empty tree, a one-node tree, a left-only chain, and duplicate values. Values alone are not enough without null structure markers.

class Codec:
    def serialize(self, root):
        tokens = []

        def walk(node):
            if node is None:
                tokens.append("#")
                return
            tokens.append(str(node.val))
            walk(node.left)
            walk(node.right)

        walk(root)
        return ",".join(tokens)

    def deserialize(self, data):
        tokens = iter(data.split(","))

        def build():
            token = next(tokens)
            if token == "#":
                return None
            node = TreeNode(int(token))
            node.left = build()
            node.right = build()
            return node

        return build()

Invariant: dp[i] is the number of decodings for the prefix ending before index i. A zero is valid only as part of 10 or 20. The common mistake is treating every two-digit number ending in zero as valid.

def num_decodings(s):
    if not s:
        return 0

    dp = [0] * (len(s) + 1)
    dp[0] = 1
    dp[1] = 0 if s[0] == "0" else 1

    for i in range(2, len(s) + 1):
        one = int(s[i - 1:i])
        two = int(s[i - 2:i])
        if 1 <= one <= 9:
            dp[i] += dp[i - 1]
        if 10 <= two <= 26:
            dp[i] += dp[i - 2]
    return dp[-1]

Invariant: after each house, prev1 is the best value through the current house and prev2 is the best value through the previous previous house. Test empty input, one house, two houses, all zeros, and a large value surrounded by small values.

def rob(nums):
    prev2 = 0
    prev1 = 0
    for value in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + value)
    return prev1

Return the Kahn traversal order when all nodes are processed. For streaming prerequisites, clarify whether queries must be answered online. A simple batch answer rebuilds indegrees; an online answer needs incremental cycle detection or versioned graph snapshots, depending on latency and update frequency.

First confirm the state and count repeated substring checks. Use a word set, cap candidate lengths by the longest dictionary word, and avoid unnecessary slicing where possible. If using recursion, add memoization by start index and test with repeated characters plus a dictionary that nearly matches but fails at the end.