LeetCode #133 Medium

Clone Graph

Given a reference to a node in a connected undirected graph, return a deep copy of the whole graph.

graphdfshash-table

02

Intuition

💡

A plain traversal would loop forever on cycles, and copying a node twice would break the structure. The fix is one map: original node → its clone. Before copying a node, check the map — if a clone already exists, reuse it. The map is simultaneously the visited-set and the wiring table that keeps every edge pointing at the right copy.

03

Approach

1

Why naive copy fails

Recursively copying neighbors with no memory loops forever on any cycle (A→B→A→…), and even without cycles a node reachable by two paths would be duplicated.

2

Map originals to clones

Keep seen[original] = clone. On visiting a node: if it is in the map, return the existing clone. Otherwise create the clone first, register it, then fill its neighbor list recursively — registering before recursing is what breaks cycles.

3

DFS or BFS both work

The traversal order does not matter; only the map does. DFS is shorter; BFS avoids deep recursion on long chains.

04

Solution & live demo

python

▶1class Solution:
▶2    def cloneGraph(self, node):
▶3        if not node: return None
▶4        seen = {}
▶5        def dfs(n):
▶6            if n in seen: return seen[n]
▶7            copy = Node(n.val)
▶8            seen[n] = copy          # register BEFORE recursing
▶9            copy.neighbors = [dfs(nb) for nb in n.neighbors]
▶10            return copy
▶11        return dfs(node)

05

Edge cases

Empty input (null node)

Return null immediately.

Single node with no neighbors

Clone made, empty neighbor list, no recursion.

Self-loop or cycle

Clone registered in the map before recursing, so the cycle hits the map and stops.

06

Complexity

Time

O(V + E)

Space

O(V)

Every node cloned once, every edge walked once.