Clone Graph

MediumGraphs · DFS + Hash Map🧩 Graph DFS LeetCode #133 ↗Updated Oct 30, 2026

Problem

You are handed one node of a connected, undirected graph; every Node stores an int val and a List<Node> neighbors. Build a deep copy: brand-new nodes with the same values and the same edges (in the same neighbour order), sharing no object with the original. Return the copy of the given node (or null for an empty graph).

Inputadj = [[2,4],[1,3],[2,4],[1,3]]Output[[2,4],[1,3],[2,4],[1,3]]

Inputadj = [[]]Output[[]]

Inputadj = []Output[]

0 ≤ nodes ≤ 100 · 1 ≤ val ≤ 100, unique (node i has val i) · no self-loops or repeated edges · graph is connected

Try it yourself

Java

class Solution {
    public Node cloneGraph(Node node) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Keep a map original → clone. It is both the “visited” set and the lookup that lets every edge point at the one clone of its endpoint — which is exactly what stops cycles from looping forever or creating duplicate copies.

PatternGraph DFS

Instinct Connected regions, all paths, reachability, cloning or 2-colouring a graph or grid: dive from a node, mark it, recurse into unvisited neighbours.

Memory hack Mark before you march: go deep, paint as you go, and back up only when every door is already painted.

Open the Graph DFS guide →

Approaches

Brute ForceTwo Passes: Copy Nodes, then Wire Edges

Time O(V + E)Space O(V)

Split the job. Pass 1: BFS over the original graph and create a bare copy of every node in a map. Pass 2: walk every original edge u → v and append copy(v) to copy(u). Since all clones exist before wiring, no edge can point to a missing node.

Java

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> copy = new HashMap<>();
    Deque<Node> q = new ArrayDeque<>(List.of(node));
    copy.put(node, new Node(node.val));
    while (!q.isEmpty()) { // pass 1: discover + create copies
        Node cur = q.poll();
        for (Node nb : cur.neighbors)
            if (!copy.containsKey(nb)) {
                copy.put(nb, new Node(nb.val));
                q.add(nb);
            }
    }
    for (Map.Entry<Node, Node> e : copy.entrySet()) // pass 2: wire edges
        for (Node nb : e.getKey().neighbors)
            e.getValue().neighbors.add(copy.get(nb));
    return copy.get(node);
}

Easy to reason about, but traverses the graph twice and needs a queue plus a map.

OptimalOne-Pass DFS with Clone Map

Time O(V + E)Space O(V)

cloneGraph(x) returns the clone of x: if it is already in the map, return it; otherwise create it, register it first, then recursively clone each neighbour and append the result. Registering before recursing is what makes a cycle 1–2–1 terminate.

Java

private final Map<Node, Node> clones = new HashMap<>();
public 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); // register BEFORE recursing to break cycles
    for (Node nb : node.neighbors) copy.neighbors.add(cloneGraph(nb));
    return copy;
}

Single traversal, minimal code; recursion depth is at most V (≤ 100 here).

Pro tip

Values are unique 1..100, so a Node[101] array can replace the hash map; for very deep graphs switch to the BFS form to avoid stack overflow.

At a glance

Level	Approach	Time	Space
Brute Force	Two Passes: Copy Nodes, then Wire Edges	`O(V + E)`	`O(V)`
Optimal	One-Pass DFS with Clone Map	`O(V + E)`	`O(V)`

Common pitfalls

Putting the clone in the map after the recursive calls — infinite recursion on cycles.
Reusing node.neighbors in the copy — a shallow copy, not a clone.
Forgetting the null (empty graph) input.

Interview tips

Name the map's two jobs out loud: visited-set and old→new lookup.
Clarify directed vs undirected — the same code works for both.
Mention this is the graph version of Copy List with Random Pointer.

Pattern

Graph traversal + old→new map → deep-copy any pointer structure that may contain cycles or shared nodes.

My notes saved in this browser