133. Clone Graph

Clone Graph looks like a plain traversal until you notice the graph has cycles, and suddenly a naive recursion loops forever. The fix is one map that does two jobs, and once you see that it’s a five-minute problem. It sits in the graph traversal pattern, where the same trick — remember what you’ve already visited — shows up over and over.

The problem

You’re handed a reference to one node in a connected, undirected graph. Each node holds an int value and a list of its neighbors. Return a deep copy: a whole new set of nodes with the same structure, sharing nothing with the original. (Full statement on LeetCode.)

Picture a tiny 3-cycle: node 1 points to 2, 2 to 3, 3 back to 1 (undirected, so every edge goes both ways). Your copy must have three brand-new nodes wired the same way — and crucially, node 1’s copy and node 2’s copy must both point at the same copy of node 3, not two separate ones.

Intuition: one map that clones and remembers at once

The trap is the cycle. If you just recurse into every neighbor and clone as you go, you’ll clone 1, walk to 2, walk to 3, walk back to 1, clone 1 again, and spiral off forever. You need a way to say “I’ve already made a copy of this node — here it is.”

A single Map<Node, Node> from original node to its clone handles everything. It’s both the visited set and the lookup table for finished copies. The order of operations is the whole problem: create the clone and put it in the map before you recurse into its neighbors. Then when the recursion loops back to a node you’ve started, the map already has its copy waiting, so you return it instead of building another.

Because every node is stored under its own object identity, two neighbors that reference the same original always resolve to the same clone. That’s what keeps shared neighbors shared and cycles from duplicating. With $V$ nodes and $E$ edges, you touch each node once and walk each edge once, so the work is $O(V + E)$.

Solution

Depth-first, carrying the map through the recursion:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public Node cloneGraph(Node node) {
        return dfs(node, new HashMap<>());
    }

    // clones maps each original node to its freshly built copy
    private Node dfs(Node node, Map<Node, Node> clones) {
        if (node == null) return null;              // empty graph -> nothing to copy
        if (clones.containsKey(node)) {
            return clones.get(node);                // already cloned; reuse it
        }

        Node copy = new Node(node.val);
        clones.put(node, copy);                      // record BEFORE recursing, or cycles loop forever

        for (Node neighbor : node.neighbors) {
            copy.neighbors.add(dfs(neighbor, clones));
        }
        return copy;
    }
}

That clones.put(node, copy) before the loop is the load-bearing line. Move it below the loop and the 3-cycle above never terminates. Everything else is bookkeeping: build a node, then hook up its neighbor list from clones the recursion returns.

Complexity

	Time	Space
DFS + HashMap	$O(V + E)$	$O(V)$

You visit each of the $V$ nodes once and traverse each of the $E$ edges once. The map holds one entry per node, and the recursion stack can go $O(V)$ deep in the worst case (a long chain).

In an interview

Say the cycle out loud early: “this is undirected and can have cycles, so I need a visited structure or the recursion won’t stop.” Then introduce the map as doing double duty — visited set and original-to-clone lookup — because that single idea is what’s being graded. Reach for the object reference as the key, not node.val; values happen to be unique here, but identity is the honest thing to key on and shows you’re not leaning on a coincidence in the constraints.

The classic slip is inserting the clone into the map after recursing on neighbors, which reintroduces the infinite loop you were trying to avoid. Watch for the null input too — an empty graph is a valid case. If the interviewer wants iterative, the same map works with a BFS queue: clone the start node, then dequeue and wire up neighbors, enqueuing any you haven’t cloned yet.

This “remember what you’ve visited” discipline is the spine of the whole graph traversal pattern. The cycle-safety here is the same instinct you need for Course Schedule, and if you want the gentlest on-ramp to DFS over a graph, Number of Islands is where it clicks.

References

• LeetCode 133 — Clone Graph