Skip to main content

133. Clone Graph

mediumAsked at LinkedIn

Deep-copy a connected undirected graph using BFS and a hash map — a near-literal model of how LinkedIn clones member connection graphs across data centers, making it one of the most contextually on-brand questions in their rotation.

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 in the graph contains a value (int) and a list of its neighbors (List[Node]). The graph is represented in the input as an adjacency list where nodes are labeled 1 to n.

Constraints

  • The number of nodes in the graph is in the range [0, 100]
  • 1 <= Node.val <= 100
  • Node.val is unique for each node
  • No repeated edges or 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: Node 1 connects to 2 and 4; the clone must replicate all edges without sharing Node objects.

Example 2

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

Approaches

1. Recursive DFS without visited map (buggy — shows the trap)

Naive recursion clones each node then recurses into neighbors — but without tracking already-cloned nodes, cycles cause infinite recursion. Show this to motivate the hash map.

Time
O(n+e)
Space
O(n) call stack
// BROKEN — infinite loop on cycles:
// function clone(node) {
//   if (!node) return null;
//   const copy = new Node(node.val);
//   copy.neighbors = node.neighbors.map(n => clone(n));
//   return copy;
// }

Tradeoff:

2. BFS with cloned-nodes hash map — optimal

Maintain a map from original node to its clone. BFS explores each neighbor; if unseen, create the clone and enqueue. Then wire the cloned neighbor into copy.neighbors.

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

Tradeoff:

LinkedIn-specific tips

LinkedIn interviewers use Clone Graph to test three things simultaneously: graph traversal, cycle detection via memoization, and the ability to work with arbitrary object references. Explicitly name the invariant: 'I need to clone each node exactly once, so a Map from original → clone prevents revisiting cycles.' The follow-up is nearly always 'what if the graph is disconnected?' — answer by noting that disconnected components won't be reachable from the given node, so they won't appear in the clone, which matches the spec.

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

Practice these live with InterviewChamp.AI →