22. Clone Graph

mediumAsked at Meta

Deep-copy an undirected graph — Meta's social network literally deep-copies subgraph views for privacy sandboxing, making this BFS/DFS-with-hash-map pattern a genuine engineering analog used in production systems.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

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

Constraints

1 <= Node.val <= 100
Node.val is unique for each node
No repeated edges; no self-loops
The graph is connected

Examples

Example 1

Input

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

Output

[[2,4],[1,3],[2,4],[1,3]]

Explanation: Node 1 neighbors are 2 and 4; the cloned graph has the same adjacency.

Example 2

Input

adjList = [[]]

Output

[[]]

Approaches

1. DFS with hash map

Recursively clone each node; use a map from original node to its clone to handle cycles and avoid infinite recursion.

Time: O(V+E)
Space: O(V)

function cloneGraph(node, visited = new Map()) {
  if (!node) return null;
  if (visited.has(node)) return visited.get(node);
  const clone = { val: node.val, neighbors: [] };
  visited.set(node, clone);
  for (const neighbor of node.neighbors) {
    clone.neighbors.push(cloneGraph(neighbor, visited));
  }
  return clone;
}

Tradeoff:

2. BFS with hash map

BFS from the source; create clone nodes eagerly and wire neighbors once both ends are cloned. Iterative — no stack overflow risk on large graphs.

Time: O(V+E)
Space: O(V)

function cloneGraph(node) {
  if (!node) return null;
  const map = new Map();
  map.set(node, { val: node.val, neighbors: [] });
  const queue = [node];
  while (queue.length) {
    const cur = queue.shift();
    for (const neighbor of cur.neighbors) {
      if (!map.has(neighbor)) {
        map.set(neighbor, { val: neighbor.val, neighbors: [] });
        queue.push(neighbor);
      }
      map.get(cur).neighbors.push(map.get(neighbor));
    }
  }
  return map.get(node);
}

Tradeoff:

Meta-specific tips

Meta grades on cycle handling — missing the visited map is an instant flag. They also probe the iterative (BFS) vs recursive (DFS) trade-off and will ask what happens when the social graph has millions of nodes. Articulate that BFS avoids call-stack overflow and fits naturally into a producer-consumer queue model used in Meta's infrastructure.

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 Meta interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →