Clone Graph (LC 133)

Pattern: Graph Traversal (BFS/DFS) + HashMap
Difficulty: Medium
Key Concept: Map each original node to its clone once, then wire neighbors by looking up clones in that map so you never duplicate nodes or get stuck in cycles.

Problem Statement

You are given a reference node of a connected undirected graph. Each Node has an integer val and a list neighbors of adjacent nodes.

Return a deep copy of the graph: new nodes with the same structure and values, but no shared Node objects with the original.

Input: Node node — the node you start from (the whole graph is reachable).
Output: Node — the corresponding node in the cloned graph (same val, cloned neighbors).

Example (conceptually): If 1 — 2 and 1 — 4, the clone must also have 1' — 2', 1' — 4', with all new objects.

Constraints: Node count ≤ 100, 1 ≤ Node.val ≤ 100, Node.val is unique for each node in the test data.

1. Algorithm & Pseudocode

Brute force

A true “brute” on graphs is awkward because you must not copy nodes twice. A naive idea is:

Serialize the whole graph to an adjacency list keyed by val (only works if val is unique — given in this problem).
Build brand-new nodes from that list.
Reconnect using val as the key.

Why it’s brute: Extra passes, building intermediate structures, and it leans on val uniqueness rather than object identity — fragile and not the idiomatic interview solution.

Optimal

Idea: One pass over nodes with BFS or DFS; a Map<Node, Node> stores original → clone.

DFS (recursive or stack)

clone(node):
  if node is null: return null
  if map contains node: return map.get(node)

  copy = new Node(node.val)
  map.put(node, copy)

  for each neighbor in node.neighbors:
    copy.neighbors.add( clone(neighbor) )   // recursion fills map first

  return copy

BFS (queue)

if node is null: return null
map = empty
queue = [node]
map.put(node, new Node(node.val))

while queue not empty:
  curr = poll queue
  for nbr in curr.neighbors:
    if nbr not in map:
      map.put(nbr, new Node(nbr.val))
      queue.add(nbr)
    map.get(curr).neighbors.add( map.get(nbr) )

return map.get(node)

2. Step-by-Step Analysis (Beginner-Friendly)

Undirected means each edge appears in both nodes’ neighbors lists. If you clone A and then B, both must point to each other’s clones, not the originals.
Cycles exist. Without a map, DFS would loop forever or create infinite clones. The map answers: “Have I already cloned this object?”
Why clone before neighbors (DFS): You register copy in the map immediately so a back-edge to curr uses the existing clone instead of recursing infinitely.
BFS vs DFS: Same complexity; BFS uses explicit Queue, DFS uses call stack or your own stack.

3. The Dry Run

Sample graph (by val): 1 connected to 2 and 4; 2 connected to 1 and 3; 4 connected to 1; 3 connected to 2.

BFS-style map growth (start at node 1):

Step	Dequeue	Action	Map keys (original `val`)
0	—	Enqueue `1`, map `1→1'`	{1}
1	`1`	See `2`,`4`; add `2→2'`, `4→4'`; link `1'→2'`, `1'→4'`	{1,2,4}
2	`2`	See `1`,`3`; `1` known; add `3→3'`; link `2'→1'`, `2'→3'`	{1,2,3,4}
3	`4`	See `1`; link `4'→1'`	same
4	`3`	See `2`; link `3'→2'`	same

Result: structure preserved, all new node objects.

4. Java Solution

Brute Force

Idea: If val is unique, collect all nodes (BFS), sort or index by val, instantiate clones, then second pass to connect. Simpler variant shown: two-phase BFS with val → clone (only valid when val unique).

// LeetCode provides class Node { int val; List<Node> neighbors; }

import java.util.*;

class SolutionBrute {
    public Node cloneGraph(Node node) {
        if (node == null) return null;

        // Phase 1: collect all nodes
        Set<Node> seen = new HashSet<>();
        Queue<Node> q = new ArrayDeque<>();
        q.add(node);
        seen.add(node);
        while (!q.isEmpty()) {
            Node u = q.poll();
            for (Node v : u.neighbors) {
                if (seen.add(v)) q.add(v);
            }
        }

        // Phase 2: val -> new node (relies on unique val — given on LC 133)
        Map<Integer, Node> byVal = new HashMap<>();
        for (Node u : seen) {
            byVal.put(u.val, new Node(u.val));
        }

        // Phase 3: wire edges using val
        for (Node u : seen) {
            Node cu = byVal.get(u.val);
            for (Node v : u.neighbors) {
                cu.neighbors.add(byVal.get(v.val));
            }
        }
        return byVal.get(node.val);
    }
}

Time: O(V + E) — every node and edge touched.
Space: O(V) for sets, maps, and clones.

Why it’s weaker: Depends on unique val; the standard solution maps Node identity, which works even if val repeated (general graphs).

Optimal

DFS with HashMap (Node → Node)

import java.util.*;

class Solution {
    private final Map<Node, Node> cloneOf = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (cloneOf.containsKey(node)) return cloneOf.get(node);

        Node copy = new Node(node.val);
        cloneOf.put(node, copy);

        for (Node nbr : node.neighbors) {
            copy.neighbors.add(cloneGraph(nbr));
        }
        return copy;
    }
}

BFS variant

import java.util.*;

class SolutionBFS {
    public Node cloneGraph(Node node) {
        if (node == null) return null;

        Map<Node, Node> cloneOf = new HashMap<>();
        ArrayDeque<Node> q = new ArrayDeque<>();

        cloneOf.put(node, new Node(node.val));
        q.add(node);

        while (!q.isEmpty()) {
            Node cur = q.poll();
            for (Node nbr : cur.neighbors) {
                if (!cloneOf.containsKey(nbr)) {
                    cloneOf.put(nbr, new Node(nbr.val));
                    q.add(nbr);
                }
                cloneOf.get(cur).neighbors.add(cloneOf.get(nbr));
            }
        }
        return cloneOf.get(node);
    }
}

Time: O(V + E) — each node enqueued/popped once; each edge examined twice in undirected form.
Space: O(V) — map + queue/recursion stack.

5. The “Java vs. Others” Edge

Use HashMap<Node, Node> with reference keys — Java hashes object identity by default for custom classes unless you override equals/hashCode. LeetCode’s Node uses identity, which matches “clone each physical node once.”
ArrayDeque<Node> is preferred over LinkedList for BFS queues (fewer allocations, no Stack legacy API).
Recursion depth equals graph depth; with |V| ≤ 100 it is fine on JVM; for huge graphs, prefer iterative DFS with an explicit Deque.

6. Complexity Summary

Approach	Time	Space	Notes
Brute (collect + val→clone + wire)	O(V + E)	O(V)	Correct on LC due to unique `val`; not general
Optimal DFS/BFS + Map<Node,Node>	O(V + E)	O(V)	Standard, works by node identity, handles cycles

ASCII: Original vs clone (triangle 1—2—3—1)

Original references:          Clone references:
    (1)                           (1')
   /   \                         /   \
 (2)---(3)                     (2')---(3')

Map: 1→1', 2→2', 3→3'
Undirected: each edge appears on both sides; cloning preserves both directions.