DSA AnimatorDSA animations
Clone Graph LC #133 Medium Graph · DFS · HashMap
Problem

Given a reference to a node in a connected undirected graph, return a deep copy (clone). Each node has val and neighbors. HashMap maps original→clone; register clone before recursing to break cycles.

Example
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]] (cloned)
Try Examples
Use preset examples — graph adj lists cannot be entered as text.
Approach
DFS + HashMap
Map original node → clone. If node in map → return clone (handles cycles). Create clone and put in map BEFORE recursing to avoid infinite recursion.
Graph & HashMap (original → clone)
Load an example to begin.
Variables
Current
—
Map size
—
Action
—
Neighbors
—
Step Logic
Press ▶ Play or Next Step to begin.
✓
Ready
0 / 0
Select an example and press Play.
Algorithm
1
If node in map → return clone (cache hit)
2
Create clone, put in map before recursing
3
Recurse to each neighbor, add returned clone to neighbors
Time
O(V+E)
Space
O(V)
Why HashMap Before Recurse

Putting the clone in the map before recursing into neighbors is critical. Otherwise, in a cycle (1↔2), DFS would: visit 1 → recurse to 2 → recurse to 1 → infinite recursion. With map: visit 1 → put clone1 → recurse to 2 → recurse to 1 → cache hit, return clone1.

How to solve Clone Graph

LeetCode 133 · Medium · Graph · Pattern: DFS + Hash Map

Why the obvious approach is slow

Copying a node and then naively copying each neighbour runs forever, because the graph has cycles. We need to remember which nodes are already copied.

The key idea

Use a hash map from each original node to its copy. When you visit a node, first check the map. If the node is already copied, return that copy, which also stops infinite loops. Otherwise create the copy, store it in the map, and then clone every neighbour and attach it.

Remember

Store the copy in the map before visiting neighbours. The map doubles as the visited set.

Run the animation above on your own input, or watch the 1:46 video explanation of Clone Graph with a dry run and Java code.

More Graph problems