LeetCode · #133

Clone Graph Solution

Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Each node has a value and a list of neighbors.

01
Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #133

🏗️

Pattern

Graph — DFS/BFS with HashMap old→new

Given a reference to a node in a connected undirected graph, return a deep copy. Each node contains int val and List<Node> neighbors. Nodes are labeled 1 to n. The graph may contain cycles.

Example
Input: adjList = [[2,4],[1,3],[2,4],[1,3]] // Node 1 ↔ 2 ↔ 3 ↔ 4 ↔ 1 (a cycle of 4 nodes) Output: Deep copy of the same graph structure
Constraints
• 0 ≤ n ≤ 100 (n = number of nodes) • 1 ≤ Node.val ≤ 100 • No repeated edges, no self-loops • Graph is connected (if non-empty)
02
Section Two · Approach 1

Naive DFS Without Cycle Tracking

Recursively clone each node by creating a new node and cloning all its neighbors. Without tracking already-cloned nodes, cycles cause infinite recursion — the DFS enters an infinite loop following back edges.

Why it fails

The graph can contain cycles (e.g., node 1 → node 2 → node 1). Without a visited map, the DFS follows 1→2→1→2→... forever, causing a stack overflow.

The fix — HashMap old→new
Key insight: Maintain a HashMap<Node, Node> mapping each original node to its clone. Before recursing into a neighbor, check if it's already in the map. If yes, return the existing clone — breaking the cycle. If no, create the clone first (add to map), then wire up neighbors. The map serves as both a visited set and a clone registry.
Java — BFS with HashMap
import java.util.*; class Solution { public Node cloneGraph(Node node) { if (node == null) return null; Map<Node,Node> map = new HashMap<>(); Queue<Node> q = new LinkedList<>(); map.put(node, new Node(node.val)); q.offer(node); while (!q.isEmpty()) { Node cur = q.poll(); for (Node nb : cur.neighbors) { if (!map.containsKey(nb)) { map.put(nb, new Node(nb.val)); // create clone, mark visited q.offer(nb); } map.get(cur).neighbors.add(map.get(nb)); // wire cloned neighbor } } return map.get(node); } }
Python — BFS with HashMap
from collections import deque class Solution: def cloneGraph(self, node: 'Node') -> 'Node': if not node: return None clones = {node: Node(node.val)} q = deque([node]) while q: cur = q.popleft() for nb in cur.neighbors: if nb not in clones: clones[nb] = Node(nb.val) # clone + mark q.append(nb) clones[cur].neighbors.append(clones[nb]) return clones[node]
MetricValue
TimeO(V + E) — every node and edge visited once
SpaceO(V) — HashMap + BFS queue
03
Section Three · Approach 2

Recursive DFS with HashMap — O(V+E)

Recursively clone each node. The HashMap breaks cycles: check if a node is already cloned before recursing. If cloned, return the existing clone immediately — this is both the visited check and the cycle breaker.

💡 Mental model: Picture a photocopier that also keeps a receipt book. Every time you copy a document, you staple the receipt to the original and write the copy's location on it. If someone asks you to copy a document that already has a receipt, you just hand them the existing copy — no need to copy it again. The receipt book is the HashMap: it maps each original node to its clone, preventing you from entering an infinite copying loop when the graph cycles back to a document you've already copied.
Algorithm — DFS with clone map
  • Base case: if node == null, return null.
  • Cycle check: if node is already in cloneMap, return cloneMap.get(node).
  • Create: make a new node with same val, put in map immediately (before recursing — critical for cycles).
  • Recurse: for each neighbor, recursively clone and add to the new node's neighbors list.
  • Return the new clone.
🎯 When to recognize this pattern:
  • Any "deep copy of a graph / linked list with random pointers" problem.
  • The signal is a data structure with references that may form cycles.
  • The HashMap pattern solves LC 138 (Copy List with Random Pointer) with identical logic — map original to clone, then wire up pointers.
  • The key: always add to the map before recursing into neighbors.
Why add to map before recursing:
  • If you create the clone and add to map only after processing all neighbors, you'll recurse infinitely on cycles before ever adding anything.
  • Adding to the map first — even before setting up neighbors — breaks the cycle because the second time you encounter that node, it's already in the map and you return immediately.
04
Section Four · Trace

Visual Walkthrough

Trace DFS cloning a 4-node cycle: 1↔2↔3↔4↔1. Starting from node 1.

Clone Graph — DFS with HashMap (4-node cycle)
Original graph (left) and clone being built (right). HashMap entries shown center. Original 1 2 4 3 HashMap (old→clone) 1 → clone(1) ←added first 2 → clone(2) 3 → clone(3) 4 → clone(4) All 4 entries after DFS Clone (deep copy) 1' 2' 4' 3' DFS call order: dfs(1) → map[1]=clone(1). Recurse into neighbors [2, 4]. dfs(2) → map[2]=clone(2). Recurse [1, 3]. dfs(1): 1 already in map → return clone(1). dfs(3) → map[3]=clone(3). Recurse [2,4]. dfs(3) → [2 in map: return clone(2)]. dfs(4) → map[4]=clone(4). Recurse [3,1]: both in map → return clones. All 4 nodes cloned. All neighbor lists wired to clones. No infinite loop due to map checks. return clone(1) ✓
05
Section Five · Implementation

Code — Java & Python

Java — DFS with clone map
import java.util.*; class Solution { private Map<Node, Node> cloneMap = new HashMap<>(); public Node cloneGraph(Node node) { if (node == null) return null; if (cloneMap.containsKey(node)) return cloneMap.get(node); // already cloned — break cycle Node clone = new Node(node.val); cloneMap.put(node, clone); // add BEFORE recursing — critical for (Node nb : node.neighbors) clone.neighbors.add(cloneGraph(nb)); return clone; } }
Python — DFS with clone map
class Solution: def cloneGraph(self, node: 'Node') -> 'Node': clones = {} def dfs(n: 'Node') -> 'Node': if n in clones: return clones[n] # already cloned — break cycle clone = Node(n.val) clones[n] = clone # add BEFORE recursing for nb in n.neighbors: clone.neighbors.append(dfs(nb)) return clone return dfs(node) if node else None
06
Section Six · Analysis

Complexity Analysis

ApproachTimeSpaceTrade-off
DFS without map (broken)O(∞)O(∞)Infinite recursion on cycles
BFS with HashMapO(V + E)O(V)Iterative — no stack overflow; slightly more code
DFS with HashMap ← optimal O(V + E) O(V) Clean recursive code; map serves as both visited set and clone registry
BFS vs DFS for graph cloning:
  • Both are O(V+E). DFS requires O(V) call stack space in addition to the HashMap.
  • BFS uses an explicit queue (O(V)) but no call stack.
  • For very large graphs (V=100 per constraints — fine either way), BFS is safer in production.
  • Both are valid in interviews.
07
Section Seven · Edge Cases

Edge Cases & Pitfalls

CaseInputWhy It Matters
Null inputnode = nullEmpty graph. Return null immediately — no map lookup needed.
Single node, no neighborsNode(1, [])Clone with empty neighbors list. DFS returns immediately after creating clone.
Cycle of 21↔2DFS(1) creates clone(1), recurse into 2. DFS(2) creates clone(2), recurse into 1 — already in map, return clone(1). ✓
Star graphCenter + N leavesCenter has N neighbors, leaves have 1 each. DFS fans out correctly.
Adding to map after recursingany cycleIf you add to map only after the recursive call returns, cycles cause infinite recursion before any map entry is ever created.
Negative or zero node valuesNot possible per constraintsNode.val ∈ [1,100] — no edge case here. The algorithm is value-agnostic anyway.
⚠ Common Mistake: Adding cloneMap.put(node, clone) after the neighbor recursion loop instead of before. Consider node A ↔ node B. DFS(A) creates clone(A), recurses into B. DFS(B) creates clone(B), recurses into A — but A is not yet in the map (you haven't returned from the A recursion yet), so DFS(A) is called again, causing infinite recursion. Always put the new clone into the map before iterating over neighbors.

← Back to Graph problems