The O(n) Club: Clone Graph (LeetCode 133) Without Spawning Infinite Twins

The O(n) Club: Clone Graph (LeetCode 133) Without Spawning Infinite Twins

⚡ TL;DR

You’ve got a connected undirected graph, and you need to make a deep clone of it—but not a horror-movie “clone.” Every node and edge should be copied, no originals or evil twin pointers lingering anywhere. Do it with DFS (or BFS if your call stack has performance anxiety) and a trusty HashMap from original nodes to their clones. Brute force? No, you can’t just new Node your way out of this one.

// Java DFS that won't accidentally spawn an infinite loop
Map<Node, Node> clones = new HashMap<>();
Node cloneGraph(Node node) {
    if (node == null) return null;
    if (clones.containsKey(node)) return clones.get(node);
    Node copy = new Node(node.val);
    clones.put(node, copy);
    for (Node neighbor : node.neighbors)
        copy.neighbors.add(cloneGraph(neighbor));
    return copy;
}

🧠 How Devs Usually Mess This Up

Here’s the usual chaos:

🔍 What’s Actually Going On

Cloning a graph is like duplicating your friend group for a parallel universe social experiment. Only, in this universe, some friends are besties with each other, and there are awkward cycles. To avoid doppelgängers running into each other (a metaphysical disaster), you need a ledger: every time you make a clone, jot it in a HashMap. The next time you meet the same original, just point to the existing clone instead of reinventing them. This preserves relationships and stops endless loops, whether you’re A/B testing a new friendship algorithm or simulating the world’s messiest dependency tree.

🛠️ PseudoCode

• Start a HashMap: Map original nodes to their shiny new clones.
  Map<Node, Node> visited = new HashMap<>();
• If your node is null: Return null. No one to clone = easy win.
• If you’ve cloned this node already: Fetch it from the map; don’t get fancy.
• Make a new node clone: Copy the value only, neighbors left empty for now.
• Mark it in the map: Before recursing, park your clone in visited.
• Clone all the neighbors: Recursively repeat for each neighbor, adding their clones to your shiny node’s neighbors list.
  // DFS keeps life simple Node cloneGraph(Node node) { if (node == null) return null; if (visited.containsKey(node)) return visited.get(node); Node copy = new Node(node.val); visited.put(node, copy); for (Node neighbor : node.neighbors) copy.neighbors.add(cloneGraph(neighbor)); return copy; }

💻 The Code

// Node definition for interviewers who demand it
typedef class Node {
    public int val;
    public List<Node> neighbors;
    public Node() { val = 0; neighbors = new ArrayList<>(); }
    public Node(int val) { this.val = val; neighbors = new ArrayList<>(); }
    public Node(int val, List<Node> neighbors) { this.val = val; this.neighbors = neighbors; }
}
 class Solution {
    private Map<Node, Node> cloned = new HashMap<>();
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (cloned.containsKey(node)) return cloned.get(node);
        Node copy = new Node(node.val);
        cloned.put(node, copy);
        for (Node neighbor : node.neighbors) {
            copy.neighbors.add(cloneGraph(neighbor));
        }
        return copy;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Cycles, cycles, cycles: If you don’t memoize, DFS turns the graph into a recursive black hole. HashMap = escape pod.
• Only value-copying: That’s not a clone, that’s a phony. Relationships and identities need to be remapped too.
• Null input edge case: Yes, interviewers toss this at you to see who panics.
• Large graphs: DFS too deep? Get a BFS queue instead. Nobody likes StackOverflow (except, ironically, interviewers).
• Complexity: O(N+M) for both time and space: N nodes and M edges, nothing more dramatic.

🧠 Interviewer Brain-Tattoo

“A graph without a clone-map is like a social network with no user IDs—be prepared for chaos and misplaced friendships.”