Skip to main content

76. Clone Graph

mediumAsked at Vercel

Deep-copy a connected undirected graph. Vercel asks this for the hash-map-while-traversing pattern — same shape as their build-graph cloning when forking a deployment branch.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; DFS + visited map expected.
  • Blind (2026-Q1)— Listed in Vercel screen pool.

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 without memo

Recurse into neighbors; create copies as you go.

Time
infinite
Space
infinite
// Infinite recursion on cycles. Must memoize.

Tradeoff: Broken; cycles in the graph cause infinite recursion.

2. DFS with visited map (optimal)

Map original node -> cloned node. On first visit, create clone, recurse into neighbors, then attach. Subsequent visits return existing clone.

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

Tradeoff: O(V + E). The map handles cycles: when we revisit an already-cloned node, we return the existing clone instead of looping. Critically: set BEFORE recursing into neighbors.

Vercel-specific tips

Vercel grades the map-set-before-recursing order. Bonus signal: explaining WHY you must set the map BEFORE the recursive neighbor calls — otherwise a cycle revisits the original and recursively creates infinite copies. Mention the BFS alternative as another way to avoid stack depth.

Common mistakes

  • Setting map AFTER recursion — infinite loop on cycles.
  • Returning the wrong node — must return the clone of the input, not the input itself.
  • Forgetting the null-node base case.

Follow-up questions

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

  • Copy List with Random Pointer (LC 138) — same pattern with a different shape.
  • Clone a graph with weighted edges.
  • Iterative DFS or BFS variant.

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 set map before recursing?

When you recurse into a neighbor that points BACK to the current node (cycle), the recursion looks up the current node in the map. If you haven't set it yet, you'd create a second clone — infinite recursion.

BFS vs DFS — which to pick?

Both work. BFS is safer for very deep graphs (no stack overflow). DFS is more concise. Vercel will accept either.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →