Skip to main content

13. Clone Graph

mediumAsked at GitHub

Deep-clone a connected undirected graph using BFS/DFS, directly analogous to forking a repository and cloning its entire commit DAG.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains a value and a list of neighbors.

Constraints

  • 1 <= Node.val <= 100
  • Node.val is unique for each node
  • No repeated edges and no self-loops

Examples

Example 1

Input
adjList = [[2,4],[1,3],[2,4],[1,3]]
Output
[[2,4],[1,3],[2,4],[1,3]]

Example 2

Input
adjList = [[]]
Output
[[]]

Approaches

1. Recursive DFS without memoization

Recursively clone each node but re-visit nodes, leading to infinite loop on cycles.

Time
O(n^2)
Space
O(n)
// Naive: visit each node, clone neighbors recursively
// Problem: cycles cause infinite recursion without a visited map

Tradeoff:

2. BFS with hash map

Use a Map from original node to cloned node to prevent revisiting. BFS from the start node, clone each new node on first encounter, then wire up neighbors from the map.

Time
O(V+E)
Space
O(V)
function cloneGraph(node) {
  if (!node) return null;
  const map = new Map();
  const queue = [node];
  map.set(node, new Node(node.val));
  while (queue.length) {
    const curr = queue.shift();
    for (const neighbor of curr.neighbors) {
      if (!map.has(neighbor)) {
        map.set(neighbor, new Node(neighbor.val));
        queue.push(neighbor);
      }
      map.get(curr).neighbors.push(map.get(neighbor));
    }
  }
  return map.get(node);
}

Tradeoff:

GitHub-specific tips

GitHub interviewers connect this to repository fork semantics — talk about how the visited map prevents double-cloning the same commit node, matching how git objects are deduplicated by SHA.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Clone Graph and other GitHub interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →