Graphs · LC #133
Clone Graph
Deep-copy an undirected connected graph using a hash map from original nodes to clones, which also serves as the visited set to handle cycles.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains an integer value and a list of its neighbors. The graph is represented in the adjacency list format.
Sample I/O
Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: Deep clone of the same graph structure Input: adjList = [[]] Output: [[]] (single node, no neighbors)
Time: O(V+E) · Space: O(V)
Intuition
How to Think About It
Intuition
DFS/BFS the graph. Before cloning a node, check if it already exists in a map of original→clone. If yes, return the existing clone (handles cycles and shared neighbors). If no, create the clone, register it immediately, then recursively clone all neighbors.
Core Concept
Hash map as both visited set and clone registry. DFS: if node in map return map[node]; create clone, store in map before recursing into neighbors (critical order - prevents infinite loops on cycles). Clone neighbors list by appending recursively cloned nodes.
When to use
Deep copying any graph/tree structure with potential cycles or shared nodes; serializing/deserializing object graphs; creating isolated snapshots of mutable graph state.
When NOT to use
Shallow copy scenarios where shared references are acceptable. When the graph is a DAG with no cycles, simpler recursive clone without visited map might suffice (but the map adds safety).
Key Insights
What to Know Cold
- The map must be populated BEFORE recursing into neighbors - otherwise cycles cause infinite recursion.
- The map serves double duty: visited set (prevent re-processing) and clone registry (return same clone for same original).
- BFS variant works equally well: process node, create clone, enqueue unvisited neighbors.
- Null input edge case: return null immediately before any map lookups.
- This pattern generalizes to any deep-copy of a structure with back-references (e.g., object graphs, DOM trees).
1 example
Worked Examples
DFS with original→clone map
4-node graph: 1-2, 1-4, 2-3, 3-4.
Recursive DFS; register clone in map before recursing neighbors.
function cloneGraph(node: _Node | null): _Node | null {
const visited = new Map<_Node, _Node>();
function dfs(n: _Node | null): _Node | null {
if (!n) return null;
if (visited.has(n)) return visited.get(n)!;
const clone = new _Node(n.val);
visited.set(n, clone); // register BEFORE recursing
for (const nb of n.neighbors) clone.neighbors.push(dfs(nb)!);
return clone;
}
return dfs(node);
}Output: Deep-cloned graph with identical structure and values
Tests understanding of visited-map ordering and cycle-safe deep copy. Meta and Google use this to probe DFS fluency and pointer/reference semantics.