Clone Graph

Medium#133graph

You get one node of a connected undirected graph; each node has a value and a list of its neighbours. Return a deep copy: new nodes with the same values and the same edges, and no link of the copy may lead to an old node. Our graph: a triangle 1 – 2 – 3 with a tail 3 – 4 – 5, and we get node 1. The answer is node 1′ of a new graph of the same shape: 1′ – 2′ – 3′ with the tail 3′ – 4′ – 5′.

133 Clone GraphWalkthrough · 1×

Example: copy the triangle 1 – 2 – 3 with the tail 3 – 4 – 5, starting from node 1. The copy is drawn on the right, its nodes marked ′.

graphcopy12345copies—clone callstop on the right—
not reached yetwaiting on the call stackcurrent callnext neighbour; a copy taken from the mapcopied with all its neighbours

copies = empty map: for every old node, its copy

01/55
restart · back · play · step
Speed
1function cloneGraph(node):
2 copies = empty map // old node → its copy
3 return clone(node)
4
5function clone(node):
6 if node in copies:
7 return copies[node]
8 copy = new node with node.val
9 copies[node] = copy // before the neighbours
10 for next in node.neighbors:
11 copy.neighbors.add(clone(next))
12 return copy
state
node
1
next
–
copy
–
copies
{}
click a step to go back

← → step · space play/pause

Why it works

  1. A depth-first walk from the given node reaches every node of a connected graph, and clone(node) copies each one it reaches.
  2. A cycle brings the walk back to a node it has already started, and a node can be reached from two sides, like 3 here. The map old → copy is filled before the neighbours are visited, so such a node is found in it and its copy is reused: no second copy, no endless loop.
  3. Every neighbour of a copy is what clone returned, and clone returns only copies, so no link of the copy leads into the old graph.

Complexity

Time O(V + E): each node is copied once and each edge is looked at from both ends. Memory O(V): the map, and a call stack up to V deep.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.