76. Clone Graph
mediumAsked at VercelDeep-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 Sam K., 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 <= 100Node.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
adjList = [[2,4],[1,3],[2,4],[1,3]][[2,4],[1,3],[2,4],[1,3]]Example 2
adjList = [][]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.
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.