Clone Graph

Explanation & Solution

Practice Problem

Description

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 (val) and a list of its neighbors.

class Node {

val: number

neighbors: Node[]

}

The graph is represented as an adjacency list where adjList[i] lists the neighbors of node i + 1. Node values are 1-indexed.

Your function receives the graph as an adjacency list and must return a deep copy — modifying the clone should not affect the original.

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

Output: [[2,4],[1,3],[2,4],[1,3]]

Explanation: There are 4 nodes. Node 1 connects to 2 and 4. Node 2 connects to 1 and 3. Node 3 connects to 2 and 4. Node 4 connects to 1 and 3. The cloned graph has the same structure.

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

Approach

Graphs pattern

1. Handle Edge Case

If adjList is null or empty, return []

2. DFS Clone with a Map

Create a Map that maps each original node index → its cloned neighbor list
For each node:
If already cloned (map.has(nodeIdx)), return the existing clone
Otherwise, create a new empty array for this node's cloned neighbors
Store it in the map before recursing — this prevents infinite loops on cycles
Recursively clone each neighbor, then add the neighbor value to the clone

3. Why Map Before Recurse?

The graph is undirected — if node A connects to B and B connects back to A, without the map check we'd recurse infinitely
By storing the clone in the map before visiting neighbors, the second time we encounter a node we immediately return its already-created clone
The map serves double duty: visited set (prevents cycles) + old-to-new mapping

4. Collect Results

Iterate from index 0 to n - 1 and collect each cloned neighbor list into the result array

Key Insight

The core pattern is DFS + HashMap. In a real Node-based implementation, map maps original Node → cloned Node. The clone is created with the same val and an empty neighbors list, then each neighbor is recursively cloned and pushed into clone.neighbors. This is the fundamental pattern for any graph cloning problem.

Time

O(V + E)each node and edge is visited once

Space

O(V)for the map and recursion stack

Visualization

Input:

DFS Clone4 nodes, 4 edges

output—

Press play to start dfs clone

CurrentQueuedVisited

21 steps

Solution Code

Max Area of Island

Number of Provinces