Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Copy Graph

LeetCode #133Medium
Deep clone with an old→new map

Given a reference to a node in a connected undirected graph, return a deep copy of the entire graph, where each cloned node holds the same value and its own list of neighbor clones.

Asked atAmazonMetaGoogle
step 1 / 27
original graph
1
2
3
4
call stack
(empty)
DFS with old→new hash map
▸
1map = {}                      // original -> clone
2clone(u):
3    if u in map: return map[u]
4    map[u] = new Node(u.val)  // store BEFORE recursing
5    for v in u.neighbours:
6        copy = clone(v)
7        map[u].neighbours.append(copy)
8    return map[u]
state
  • map old→new{}
  • goaldeep copy

line 1Copy Graph (LeetCode 133): deep-clone a connected undirected graph. The trick is one hash map, old→new, that records each original node's clone. The map does double duty: it stops infinite loops in the cyclic graph (a node already in the map is never re-cloned), and it lets shared neighbours reconnect to the SAME clone instead of duplicating it.