18. Clone Graph

mediumAsked at Notion

Deep-copy an undirected graph while preserving all edges — the exact operation Notion's backend performs when duplicating a page with its full backlink and relation graph, making cycle-safe traversal non-negotiable.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Each node contains a value (int) and a list of its neighbors.

Constraints

1 <= number of nodes <= 100
Node values are unique and in range [1, 100]
Graph has no repeated edges and 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]]

Explanation: Node 1 neighbors: 2,4. Node 2 neighbors: 1,3. Node 3 neighbors: 2,4. Node 4 neighbors: 1,3. Deep copy preserves all edges.

Example 2

Input

adjList = [[]]

Output

[[]]

Explanation: Single node with no neighbors.

Approaches

1. DFS with visited map

Recurse through neighbors; use a Map from original node to its clone to detect cycles and avoid infinite loops.

Time: O(V + E)
Space: O(V)

function cloneGraph(node) {
  if (!node) return null;
  const visited = new Map();
  function dfs(n) {
    if (visited.has(n)) return visited.get(n);
    const clone = { val: n.val, neighbors: [] };
    visited.set(n, clone);
    for (const neighbor of n.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }
    return clone;
  }
  return dfs(node);
}

Tradeoff:

2. BFS with visited map

Use a queue; clone each node before enqueuing, link neighbors as they are dequeued — iterative, avoids call-stack growth for large graphs.

Time: O(V + E)
Space: O(V)

function cloneGraph(node) {
  if (!node) return null;
  const visited = new Map();
  visited.set(node, { val: node.val, neighbors: [] });
  const queue = [node];
  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:

Notion-specific tips

Notion's page-duplication feature has to clone relation properties, backlinks, and mentions without creating cycles — they use this problem to check you know why a visited map is mandatory, not optional. State the cycle-detection motivation before writing code.

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

Practice these live with InterviewChamp.AI →