#81 Medium Time O(V+E) Space O(V) Animated

Clone Graph

Deep clone a connected undirected graph.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Graph traversal with a visited frontier

A visited structure makes each vertex’s work happen at most once.

Approach: DFS (Hash Map)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

A visited structure makes each vertex’s work happen at most once.

Common Pitfall

Mark a node visited when it is scheduled, not after duplicate work is queued.

Description

Deep clone a connected undirected graph.

Constraints

Time Complexity: O(V+E)
Space Complexity: O(V)

Solution — DFS (Hash Map)

TimeO(V+E) SpaceO(V)

Implementation Plan

Translate the invariant into these small, testable moves.

Choose a start node or component.
Add it to the traversal frontier.
Visit valid unseen neighbors.
Repeat for every remaining component if needed.

def cloneGraph(node):
    if not node: return None
    oldToNew = {}
    
    def dfs(node):
        if node in oldToNew:
            return oldToNew[node]
            
        copy = Node(node.val)
        oldToNew[node] = copy
        for nei in node.neighbors:
            copy.neighbors.append(dfs(nei))
            
        return copy
        
    return dfs(node)

Number of Islands

Max Area of Island

Clone Graph

Steps

Description

Constraints

Tags

Solution — DFS (Hash Map)