Typorithm · medium

Clone Graph

clone-graphgraphsdeep-copyvisited-mapdfs

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Clone Graph

Graphs

DFS each node, mapping original→clone before recursing so cycles reuse the existing copy instead of looping.

Deep-copying a graph must preserve structure, including cycles, without duplicating shared nodes.

A Map from original to clone ensures each node is copied exactly once.

Registering the clone BEFORE recursing into neighbors is what lets a cycle find the partial copy and stop.

Map original nodes to clones.

Return the stored clone on revisits.

function cloneGraph(node) {
  const clones = new Map();

  function dfs(curr) {
    if (curr === null) {
      return null;
    }
    if (clones.has(curr)) {
      return clones.get(curr);
    }
    const copy = { val: curr.val, neighbors: [] };
    clones.set(curr, copy);
    for (const neighbor of curr.neighbors) {
      copy.neighbors.push(dfs(neighbor));
    }
    return copy;
  }

  return dfs(node);
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Original → copy

Map each original node to its single clone.

const clones = new Map()

2. Reuse clone

Return the existing copy to avoid infinite loops on cycles.

if (clones.has(curr)) {
      return clones.get(curr);
    }

3. Shallow shell

Create the clone before recursing so cycles resolve.

const copy = { val: curr.val, neighbors: [] }

4. Register first

Record the clone before visiting neighbors.

clones.set(curr, copy)

5. Clone neighbors

Recursively clone and link each neighbor.

copy.neighbors.push(dfs(neighbor))

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.