Clone Graph

mediumTests passed 2026-11-11v1.0.0
TC: O(V + E)|SC: O(V)
GraphsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Maintain `clones = { origNode: newNode }` *before* recursing into neighbors so cycles short-circuit immediately to the already allocated copy without infinite loops.

2. Complexity Bounds & Proof

Visits each node once and traverses each edge once per endpoint.

3. Minimal Idiomatic Code

def cloneGraph(node: Optional[Node]) -> Optional[Node]:
    if not node:
        return None
    clones = {}
    def dfs(u: Node) -> Node:
        if u in clones:
            return clones[u]
        copy = Node(u.val)
        clones[u] = copy
        for nbr in u.neighbors:
            copy.neighbors.append(dfs(nbr))
        return copy
    return dfs(node)

4. Failure Modes & Interview Follow-ups

Pitfalls:- Registering the clone *after* neighbor DFS causes infinite recursion on cycles. - Failing to handle `node is None` input crashes on empty graph.
Follow-ups:- Copy List with Random Pointer uses the identical `{ origNode: cloneNode }` bijection trick.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Course Schedule (O(V + E))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.