How do you solve Clone Graph?

Implement a recursive DFS function that, given a node, returns its clone. The function first checks if the node is already cloned in the map; if so, it returns the clone immediately. Otherwise, it creates a new node clone, stores it in the map, and recursively clones all neighbors, appending them to the clone's neighbors list. Finally, the function returns the clone. This approach guarantees a deep copy of the entire graph with O(N + E) time complexity.

What pattern does Clone Graph use?

The Pattern: DFS (Graph Cloning with Memoization) The Heuristic: When cloning graphs with cycles, use DFS combined with a map from original nodes to cloned nodes to avoid infinite recursion and ensure each node is cloned exactly once.

Clone Graph — DFS

Q: What is the time complexity of Clone Graph?

O(N + E). Each node is visited once and each edge is explored once during the DFS traversal. The memoization map ensures no node is processed multiple times, resulting in linear time relative to the number of nodes and edges.

Problem

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph such that each node in the cloned graph has the same value and neighbors as the original graph.

The number of nodes in the graph is in the range [0, 100]
1 ≤ Node.val ≤ 100
Node.val is unique for each node
The graph is connected and undirected

Example

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

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

The input graph has 4 nodes with edges between 1-2, 1-4, 2-3, and 3-4. The algorithm starts cloning from node 1. It creates a copy of node 1, then recursively clones its neighbors 2 and 4. For neighbor 2, it clones node 2 and its neighbors 1 and 3. When it encounters node 1 again, it returns the already created copy to avoid infinite recursion. This process continues until all nodes are cloned, preserving the graph structure without duplication.

Approach

Straightforward Solution

A brute-force approach would attempt to clone nodes without tracking visited nodes, leading to infinite recursion or duplicated nodes. Another naive approach is to clone nodes iteratively but without memoization, which complicates neighbor linking and risks duplication.

Core Observation

Cloning a graph requires creating new nodes for each original node and replicating their neighbor relationships. Because graphs may contain cycles, naive recursion risks infinite loops unless visited nodes are tracked and reused.

Path to Optimal

Preview

The key insight is to use DFS with a hash map (memoization) that maps original nodes to their cloned counterparts. This map acts as a cache to prevent re-cloning nodes and to handle cycles gracefully…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement a recursive DFS function that, given a node, returns its clone. The function first checks if the node is already cloned in the map; if so, it returns the clone immediately…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(N + E)

Each node is visited once and each edge is explored once during the DFS traversal. The memoization map ensures no node is processed multiple times, resulting in linear time relative to the number of nodes and edges.

Space

O(N)

The recursion stack can grow up to O(N) in the worst case, and the memoization map stores a cloned node for each original node, both scaling linearly with the number of nodes.

Solution

Python

1# Definition for a Node.
2# class Node:
3#     def __init__(self, val = 0, neighbors = None):
4#         self.val = val
5#         self.neighbors = neighbors if neighbors is not None else []
6
7class Solution:
8    def cloneGraph(self, node: 'Node') -> 'Node':
9        if not node:
10            return None
11        
12        old_to_new = {}
13
14        def dfs(node):
15            if node in old_to_new:
16                return old_to_new[node]
17            
18            copy = Node(node.val)
19            old_to_new[node] = copy
20            for neighbor in node.neighbors:
21                copy.neighbors.append(dfs(neighbor))
22            return copy
23
24        return dfs(node)

Step-by-Step Solution

1

Handle Null Input to Return Empty Clone

9if not node:
10    return None

Objective

To immediately return None if the input graph is empty, avoiding unnecessary processing.

Key Insight

An empty input graph means there is nothing to clone. Early returning None handles this edge case cleanly and prevents errors in the recursive cloning logic.

Interview Quick-Check

State & Boundaries

Check if the input node is None before starting DFS to handle empty graph edge case.

2

Initialize Memoization Map to Track Cloned Nodes

To create a dictionary that maps original nodes to their cloned counterparts, enabling cycle detection and reuse.

3

Recursively Clone Nodes and Their Neighbors Using DFS

To perform a depth-first traversal that clones each node and recursively clones all its neighbors, building the full deep copy.

4

Return the Cloned Graph Starting from Input Node

To initiate the cloning process by calling DFS on the input node and returning the fully cloned graph.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 15 Critical

if node in old_to_new:

Return the clone if the node has already been cloned.

This memoization check prevents infinite recursion by returning the existing clone immediately when a node is revisited.

Line 19 Critical

old_to_new[node] = copy

Store the clone in the map keyed by the original node.

Storing the clone before recursive neighbor cloning is critical to handle cycles and allow neighbor recursion to reference this clone.

Line 12 Critical

old_to_new = {}

Initialize a dictionary to map original nodes to their clones.

This map is essential to track cloned nodes, prevent infinite recursion on cycles, and ensure shared neighbors are cloned once and reused.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why is it necessary to use a map from original nodes to cloned nodes during DFS cloning of a graph?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Clone Graph from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Clone Graph drill

or drill a free problem

1	`# Definition for a Node.`
2	`# class Node:`
3	`# def __init__(self, val = 0, neighbors = None):`
4	`# self.val = val`
5	`# self.neighbors = neighbors if neighbors is not None else []`
6
7	`class Solution:`
8	`def cloneGraph(self, node: 'Node') -> 'Node':`
9	`if not node:`
10	`return None`
11
12	`old_to_new = {}`
13
14	`def dfs(node):`
15	`if node in old_to_new:`
16	`return old_to_new[node]`
17
18	`copy = Node(node.val)`
19	`old_to_new[node] = copy`
20	`for neighbor in node.neighbors:`
21	`copy.neighbors.append(dfs(neighbor))`
22	`return copy`
23
24	`return dfs(node)`