Skip to main content

133. Clone Graph

mediumAsked at Snap

Snap's friend-graph data model is serialized and deep-cloned for A/B test sandboxes and recommendation experiments — clone graph is the interview distillation of that operation.

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 (int) and a list of its neighbors. The graph has at most 100 nodes with unique values 1–100.

Constraints

  • The number of nodes is in the range [0, 100]
  • 1 <= Node.val <= 100
  • Node.val is unique for each node
  • There are 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]] (deep copy)

Example 2

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

Approaches

1. BFS with visited map

Use a Map from original node to its clone as the visited structure. BFS from the starting node: for each node, clone it if not already cloned, then process each neighbor the same way.

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

Tradeoff:

2. DFS with memoization

Recursive DFS: before cloning a node check the memo map. If already cloned, return the clone immediately to handle cycles. Build the neighbor list recursively.

Time
O(V + E)
Space
O(V) call stack + memo
function cloneGraph(node) {
  if (!node) return null;
  const memo = new Map();
  function dfs(curr) {
    if (memo.has(curr)) return memo.get(curr);
    const clone = new Node(curr.val);
    memo.set(curr, clone);
    for (const neighbor of curr.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }
    return clone;
  }
  return dfs(node);
}

Tradeoff:

Snap-specific tips

Snap's social graph has cycles (mutual friendships), so the memo/visited map for cycle detection is non-negotiable. The interviewer will add 'what if nodes can have arbitrary metadata maps?' — your clone needs to deep-copy those too. Discuss JSON.parse(JSON.stringify()) limitations (no functions, no circular refs) to show you understand why a manual DFS clone is necessary.

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

Practice these live with InterviewChamp.AI →