Skip to main content

20. Clone Graph

easyAsked at Tripadvisor

Deep-copy a connected undirected graph — Tripadvisor mirrors this challenge when duplicating destination networks or recommendation graphs for A/B testing without corrupting the live data structure.

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 value (int) and a list of its neighbors. The graph is represented in the test case using an adjacency list. Node values are unique and equal to the node's 1-based index.

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
  • There are no repeated edges and no self-loops in the graph

Examples

Example 1

Input
adjList = [[2,4],[1,3],[2,4],[1,3]]
Output
[[2,4],[1,3],[2,4],[1,3]]

Explanation: A deep copy of the 4-node cycle graph where node 1 connects to 2 and 4.

Example 2

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

Approaches

1. Brute force BFS with map

BFS from the start node. Use a hash map from original node to its clone to detect already-visited nodes and wire neighbor references.

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

Tradeoff:

2. DFS with memoization map

Recursively clone each node; store clones in a map keyed by the original node to break cycles and prevent infinite recursion.

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:

Tripadvisor-specific tips

At Tripadvisor, this problem signals whether you understand reference semantics in graph structures — critical for cloning recommendation graphs before running experiments. The key insight interviewers look for is the visited map acting as both cycle-breaker and a cache. Mention the tradeoff between DFS (cleaner code) and BFS (no call-stack risk on large destination networks with thousands of 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 Tripadvisor interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →