LeetCode 133 ·
Medium
Clone Graph
Return a deep copy of a connected undirected graph.
Try it
Step through the core mechanic. The simulator below runs the dfs shape this problem is built on.
Walk the pattern
No dedicated step-through for this one yet. The shape is DFS — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
DFS/BFS with a hash map from original node to its clone. Create the clone on first visit; the map both prevents infinite loops on cycles and lets you wire neighbour links.
| Aspect | Value |
|---|---|
| Pattern | DFS |
| Recognise it by | Deep-copy a graph with cycles. |
| Time complexity | O(V+E) |
| Space complexity | O(V) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.