March 24
Clone Graph
How to deep-copy a graph with cycles by keeping a clear mapping from old nodes to new ones.
Graphs Intermediate 20 min TypeScript
Given a node in a connected undirected graph, return a deep copy of the graph.
Each node has:
valneighbors
In the original problem, the input is usually a reference to node 1.
In the SeniorPath playground, to keep comparison deterministic, use an adjacency list:
adjList[i]represents the neighbors of nodei + 1
And return a new adjacency list with the same structure.
Example:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
The output looks the same, but it must be an independent copy.
What to notice before coding
- The challenge is copying structure with cycles, not only values.
- Without memorizing cloned nodes, you will create duplicates or loop forever.
- The important map goes from the old node to the new node.
Common mistakes
- reusing original neighbors inside the clone
- creating a new copy every time you see the same node again
Step 1 - Understand what deep copy means here
It is not enough to return a structure with the same values.
Deep copy means:
- every node in the copy is new
- connections in the copy point to nodes in the copy
- nothing in the copy points back to the old graph
Step 2 - Start with the flattened playground version
In the playground, the input already comes as an adjacency list.
So the most direct copy is:
- create a new array
- copy each neighbor list
That solves the deterministic playground representation.
But it still does not teach the heart of the original problem.
Step 3 - See why the original problem is trickier
When the input is a node with references to neighbors:
- the graph can contain cycles
- you may see the same node many times
If every repeated visit creates a new node, the copy breaks.
Step 4 - Remember what was already cloned
The strong rule is:
- if the old node already has a copy, reuse it
- if it does not, create it and register it before exploring neighbors
That "register first" step is what prevents an infinite loop in DFS.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function cloneGraphFromAdjList(adjList: number[][]): number[][] {
// return a deep copy of the adjacency list
return []
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(V + E)
Space: O(V)
Solution 1 - Copy the playground adjacency list
Good baseline for the flattened and deterministic representation.
export function cloneGraphFromAdjList(adjList: number[][]): number[][] {
return adjList.map((neighbors) => [...neighbors])
}It works for the playground adaptation.
But it is not the core idea of the original problem, where the input is a graph of connected objects.
Solution 2 - Clone the real graph with an old -> new hash map and DFS
Now the faithful version uses graph nodes and memorizes the copies.
type GraphNode = {
val: number
neighbors: GraphNode[]
}
function buildGraph(adjList: number[][]): GraphNode | null {
if (adjList.length === 0) {
return null
}
const nodes = adjList.map((_, index) => ({ val: index + 1, neighbors: [] as GraphNode[] }))
for (let index = 0; index < adjList.length; index += 1) {
nodes[index].neighbors = adjList[index].map((neighborValue) => nodes[neighborValue - 1])
}
return nodes[0]
}
function cloneGraph(node: GraphNode | null): GraphNode | null {
if (node === null) {
return null
}
const clones = new Map<GraphNode, GraphNode>()
function dfs(current: GraphNode): GraphNode {
const existing = clones.get(current)
if (existing) {
return existing
}
const copy: GraphNode = { val: current.val, neighbors: [] }
clones.set(current, copy)
for (const neighbor of current.neighbors) {
copy.neighbors.push(dfs(neighbor))
}
return copy
}
return dfs(node)
}
function toAdjList(node: GraphNode | null): number[][] {
if (node === null) {
return []
}
const result: number[][] = []
const queue: GraphNode[] = [node]
const seen = new Set<number>([node.val])
while (queue.length > 0) {
const current = queue.shift()!
result[current.val - 1] = current.neighbors.map((neighbor) => neighbor.val)
for (const neighbor of current.neighbors) {
if (!seen.has(neighbor.val)) {
seen.add(neighbor.val)
queue.push(neighbor)
}
}
}
return result
}
export function cloneGraphFromAdjList(adjList: number[][]): number[][] {
const root = buildGraph(adjList)
const clonedRoot = cloneGraph(root)
return toAdjList(clonedRoot)
}The strong insight here is that the map is not “value to value”.
The map is:
- old node to new node
What to say in the interview
A strong short explanation would be:
Deep-copying a graph with cycles requires memoization. I use a map from the original node to the cloned node. The first time I see a node, I create the copy and register it immediately. If I see that node again, I reuse the existing copy. That prevents both infinite loops and duplicated nodes.
That shows that you:
- understood why cycles change the problem
- separated old identity from new identity
- justified why the map is necessary
When this pattern shows up again
This pattern comes back when you need to:
- deep-copy a structure with references
- traverse a cyclic graph
- use DFS or BFS with memoization
- maintain a mapping between old entities and new entities during a transformation
The point is not memorizing
cloneGraph.
The point is learning when copying without memory breaks the structure identity.