Skip to main content

14. Clone Graph

easyAsked at Quora

Deep-copy a connected undirected graph — Quora uses this pattern to test how you replicate user-question relationship networks without corrupting shared references between nodes.

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 val (integer) and a list of its neighbors. The graph is represented as an adjacency list where each node's value equals its 1-indexed position.

Constraints

  • 1 <= Node.val <= 100
  • Node.val is unique for each node
  • 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]]

Explanation: Four nodes: 1-2-3-4 form a cycle. The clone has identical structure with new node objects.

Example 2

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

Explanation: Single node with no neighbors.

Approaches

1. Brute force BFS without visited map

Traverse and clone each node; without a visited map, cycles cause infinite loops.

Time
O(V + E)
Space
O(V)
// Naive — will loop on cycles. Shown for contrast only.
function cloneGraph(node) {
  if (!node) return null;
  const clone = { val: node.val, neighbors: [] };
  for (const neighbor of node.neighbors) {
    clone.neighbors.push(cloneGraph(neighbor)); // cycles infinite-loop here
  }
  return clone;
}

Tradeoff:

2. BFS with hash-map memoisation

Use a Map from original node to its clone; any time you revisit a node, return the already-created clone. Standard graph-copy pattern using BFS.

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

Tradeoff:

Quora-specific tips

Quora interviewers care about cycle safety — they map their Q&A graph internally and need engineers who instinctively reach for a visited-map before traversing. Articulate why you memoize clones rather than nodes.

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

Practice these live with InterviewChamp.AI →