Skip to main content

20. Clone Graph

mediumAsked at Postman

Deep-copy a connected undirected graph given a node reference.

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 holds a value and a list of its neighbors.

Constraints

  • 0 <= nodes <= 100
  • 1 <= node.val <= 100
  • node.val is unique
  • No self-loops or duplicate edges

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. DFS without memo

Recurse on each neighbor without memoizing — quickly explodes into an infinite loop on cycles.

Time
infinite on cycles
Space
—
// wrong: clone(n) returns new Node(n.val, n.neighbors.map(clone)) — cycles loop forever

Tradeoff:

2. BFS with visited map

Map original -> clone. BFS the graph; on first visit create a clone and queue; for each neighbor link clones via the map.

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

Tradeoff:

Postman-specific tips

Postman uses graph cloning when forking a Collection (with shared sub-folder refs) so calling out cycle handling explicitly is what separates the hire from the no-hire.

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

Practice these live with InterviewChamp.AI →