← Back to DSA Animator
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.