Skip to main content

30. Clone Graph

mediumAsked at Doordash

Deep-clone an undirected connected graph — Doordash uses this graph-traversal pattern when replicating delivery zone topology across regional data centers for failover and load balancing.

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

Problem

Given a reference of 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 input as an adjacency list.

Constraints

  • The number of nodes is in the range [0, 100]
  • 1 <= Node.val <= 100; Node.val is unique for each node
  • No repeated edges and no self-loops
  • Graph is connected and undirected

Examples

Example 1

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

Explanation: Deep clone of a 4-node cycle graph. Each cloned node has the same neighbors as the original.

Example 2

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

Explanation: Single node, no neighbors.

Approaches

1. BFS with visited map

Use a queue to traverse the graph level by level. Maintain an oldToNew map to detect already-cloned nodes and wire neighbor references correctly.

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

Tradeoff:

2. DFS recursive with visited map

Recursively clone each node; use a hash map to break cycles. On revisit return the already-cloned instance.

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

Tradeoff:

Doordash-specific tips

Doordash asks this to test your comfort with graph cycle-breaking — the visited map is mandatory, not optional. They want to hear you explicitly say: 'I create the clone before recursing into neighbors, otherwise a cycle causes infinite recursion.' The DFS solution is typically cleaner to express. Follow-ups go to serialization/deserialization of the graph (classic distributed-systems question), and extending to a directed weighted graph — which maps directly to their road-network topology.

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

Practice these live with InterviewChamp.AI →