Skip to main content

20. Clone Graph

mediumAsked at Figma

Deep-copy a connected undirected graph including all cycles. Figma frames this as a duplicate-component operation where the scene graph contains symbol references and cycles must be preserved without infinite recursion.

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

Problem

Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Each node has an int val and a list of neighbors. Preserve structural identity — cycles must remain cycles in the clone.

Constraints

  • Number of nodes <= 100
  • 1 <= Node.val <= 100
  • 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]]

Example 2

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

Approaches

1. Naive recursive copy

Recurse on every neighbor without memoizing; explodes into infinite recursion on the first cycle.

Time
infinite on cycles
Space
infinite on cycles
function clone(node) {
  if (!node) return null;
  return new Node(node.val, node.neighbors.map(clone));
  // BUG: infinite recursion on any cycle
}

Tradeoff:

2. DFS with visited map

Memoize original-to-clone in a Map; on revisit, return the existing clone instead of recursing. Constant-time cycle break. Same pattern Figma uses to duplicate scene-graph subtrees containing symbol cycles.

Time
O(V + E)
Space
O(V)
function cloneGraph(node) {
  if (!node) return null;
  const map = new Map();
  const dfs = (n) => {
    if (map.has(n)) return map.get(n);
    const copy = { val: n.val, neighbors: [] };
    map.set(n, copy);
    for (const nb of n.neighbors) copy.neighbors.push(dfs(nb));
    return copy;
  };
  return dfs(node);
}

Tradeoff:

Figma-specific tips

Figma scores you on whether you mention scene-graph duplication and symbol-reference cycles unprompted — they hire candidates who think in terms of their actual product surface.

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

Practice these live with InterviewChamp.AI →