Skip to main content

30. Clone Graph

mediumAsked at Box

Deep-clone an undirected graph without duplicating shared nodes — Box uses structurally identical logic when snapshotting a file-permission graph to create an isolated copy for audit trails and compliance exports.

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 is represented in the test as an adjacency list. Node values are the same as their 1-indexed position in the list.

Constraints

  • The number of nodes in the graph 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
  • 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 connects to 2 and 4; the cloned graph has the same structure with new node objects.

Example 2

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

Approaches

1. Brute force — BFS with visited map

BFS from the start node. Maintain a map from original node to clone. For each neighbor, create a clone if not already created, then wire neighbors on the clone.

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 nb of curr.neighbors) {
      if (!visited.has(nb)) {
        visited.set(nb, new Node(nb.val));
        queue.push(nb);
      }
      visited.get(curr).neighbors.push(visited.get(nb));
    }
  }
  return visited.get(node);
}

Tradeoff:

2. Optimal — DFS with hash map

Recursive DFS: check if the node was already cloned (cycle/shared-node guard); if not, create a clone, register it, then recursively clone all neighbors.

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

Tradeoff:

Box-specific tips

Box interviewers focus on the hash map as the key mechanism — without it you enter an infinite loop on cycles, which is catastrophic in a permission graph where groups can be mutually nested. Tie this to Box's compliance snapshot feature: when Box produces an audit export of who had access to what at a point in time, they need a complete, cycle-safe deep copy of the permission graph that can be stored independently from the live system.

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

Practice these live with InterviewChamp.AI →