Skip to main content

77. Clone Graph

mediumAsked at Plaid

Deep copy a connected undirected graph. Plaid asks this because their account-link graph (user -> bank -> account -> transaction) is exactly this kind of cyclic reference structure that must be cloneable for snapshot tests.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II onsite — account-link graph clone.
  • Blind (2026)— Plaid backend OA.

Problem

Given a reference of 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 (List[Node]) of its neighbors.

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.
  • The graph is connected and all nodes can be visited starting from the given node.

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 with map

Map old node to new node. DFS the graph; on visit, clone the node, recurse for each neighbor.

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

Tradeoff: Clean. The map handles cycles — if we've already cloned a node, we return the existing clone.

2. BFS with map

Same idea, iterative.

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 queue = [node];
  while (queue.length) {
    const n = queue.shift();
    for (const nb of n.neighbors) {
      if (!map.has(nb)) {
        map.set(nb, { val: nb.val, neighbors: [] });
        queue.push(nb);
      }
      map.get(n).neighbors.push(map.get(nb));
    }
  }
  return map.get(node);
}

Tradeoff: Iterative — avoids stack overflow on huge graphs. Same asymptotic.

Plaid-specific tips

Plaid grades this on whether you handle cycles correctly. Bonus signal: explicitly mention 'check the map before cloning' as the cycle-safety step. Connect to account-link graphs where a single user can have multiple banks each with multiple accounts each with multiple transactions, sometimes with shared sub-entities.

Common mistakes

  • Not checking the map before cloning — infinite loop on a cycle.
  • Cloning the neighbors before adding the current node to the map — same infinite loop.
  • Returning the original neighbors list — must be the cloned list.

Follow-up questions

An interviewer at Plaid may pivot to one of these next:

  • Clone a directed graph.
  • Clone with edge weights.
  • Serialize and deserialize a graph.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why map old to new and not new to old?

We look up by original node identity when traversing. Mapping new -> old would require knowing the new node first, which is what we're constructing.

BFS or DFS — does it matter?

Same asymptotic. DFS is shorter to write; BFS is safer for deep graphs. Plaid's graphs are shallow but wide, so either works.

Practice these live with InterviewChamp.AI

Drill Clone Graph and other Plaid interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →