Clone / traverse with a visited map

54 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You are given a drawing of four nodes in a ring, 1–2–3–4–1, where each node holds a list of its neighbours, and you must make an exact copy: new nodes, same values, same connections. By hand you draw four fresh circles, write 1 to 4 in them, and draw the same four lines. Easy, because you can see the whole drawing.

A program cannot see the whole drawing; it only holds node 1 and can follow neighbour pointers. If it copies node 1, then copies neighbour 2, then from 2 copies neighbour 1 again, it makes a second copy of 1, then a second copy of 2, and never stops, because the ring has no end. The naive copy loops forever and also creates the wrong shape.

Build the structure, one piece at a time

Piece one: a map from original node to its copy. Before copying a node, look it up. If it is there, reuse the copy; if not, create the copy and record it immediately, before touching its neighbours.

Piece two: a traversal, depth-first or breadth-first, that visits each original once. The map doubles as the visited set.

Walk the ring starting at 1:

1. 1 not in map: create 1′, map = {1: 1′}. Visit its neighbours 2 and 4.
2. 2 not in map: create 2′, map = {1: 1′, 2: 2′}. Neighbours of 2 are 1 and 3. 1 is in the map: reuse 1′, wire 2′ → 1′.
3. 3 not in map: create 3′. Its neighbour 2 is in the map: wire 3′ → 2′.
4. 4 not in map: create 4′. Its neighbours 3 and 1 are both in the map: wire 4′ → 3′ and 4′ → 1′.
5. Back at 1: neighbour 4 is in the map, wire 1′ → 4′. Done: four copies, four edges mirrored.

The same skeleton, "map plus traversal", clones a linked list with random pointers, finds whether a path exists, or collects which rooms a set of keys can open; only the work done per node changes.

Why it is correct

The invariant: every original node that has been seen has exactly one copy, and it is in the map. Creating the copy before exploring neighbours is what keeps it true in a ring: when the walk comes back round to 1, the lookup finds 1′ instead of making a new one. Every edge u → v in the original becomes u′ → map[v], which exists because v is either already copied or copied on the spot, so the copy has exactly the original's edges and no others.

Why it is fast

Each node is created once and each edge is wired once; map lookups are constant time on average:

work = V + E, and memory V for the map

Without the map the walk never terminates on any graph with a cycle, so the comparison is not slow versus fast but finite versus infinite.

How to recognise it in an interview

Cues: "deep copy", "clone", "each node has a random or extra pointer", "reachable from the start", "can you reach every room". The first thing to say: "I will traverse once and keep a map from original to copy so each node is created exactly once." Clone Graph is the example above. Keys and Rooms is the same traversal with a visited set instead of a copy map: count rooms reached from room 0.

02The idea in one line

Map original→copy; create a node the first time you see it, reuse afterwards.

Reach for it when: Clone graph, copy random list, keys and rooms, find if path exists.

Cost: O(V + E) time.

03The walk-through, step by step

The video works one example: Clone Graph on a 4-node cycle. These are its captions in order, so you can follow without the video or check a step you missed.

1. Map original → clone; a node is cloned once, on first sight
2. First time at 1: create clone 1' and record it in the map
3. First time at 2: create clone 2' and record it in the map
4. 1 already in the map: reuse 1' instead of cloning again
5. First time at 3: create clone 3' and record it in the map
6. 2 already in the map: reuse 2' instead of cloning again
7. First time at 4: create clone 4' and record it in the map
8. 3 already in the map: reuse 3' instead of cloning again
9. 1 already in the map: reuse 1' instead of cloning again
10. Wire 3' → 4'
11. Wire 2' → 3'
12. Wire 1' → 2'
13. 4 already in the map: reuse 4' instead of cloning again
14. Clone finished: same shape, 4 new nodes, every edge mirrored
15. Each node and edge handled once: O(V + E)

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS shortest path (unweighted), BFS over an augmented state, 0-1 BFS (deque), DFS three-colour cycle detection, Topological sort (Kahn's), Union–Find (disjoint sets), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Minimum spanning tree, Bipartite colouring, Eulerian path (Hierholzer), Bridges / articulation (low-link), Implicit graph (states as nodes).