Skip to main content

22. Clone Graph

mediumAsked at DigitalOcean

Deep-copy an undirected graph using DFS and a visited map — directly models snapshotting a network topology for DR scenarios.

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 has a val and a list of neighbors. The clone must have newly allocated nodes with the same structure.

Constraints

  • 1 <= Node.val <= 100
  • No repeated edges, no self-loops
  • 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. BFS without hash map (incorrect without dedup)

BFS but naively create new nodes without tracking already-cloned nodes — leads to infinite loops on cycles.

Time
O(V+E)
Space
O(V)
// INCORRECT — shown to illustrate the common mistake
// Never create a node in BFS without checking the map first

Tradeoff:

2. DFS with clone map

Map each original node to its clone; on revisit return the cached clone immediately. Recursively clone all neighbors before returning — handles cycles correctly.

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

Tradeoff:

DigitalOcean-specific tips

DigitalOcean cares about deep-copy semantics in infrastructure automation; tie this to copying a VPC network topology when snapshotting for disaster recovery.

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

Practice these live with InterviewChamp.AI →