0133.Clone Graph

Link: 133. Clone Graph
Track: NeetCode150

Question

Restate the problem

• Given a starting node of undirected graph
• Clone each node, recreate the same connections between the cloned node as in the original graph
• Return the cloned starting clone node

Confused

• Given a node, but the example shows list of list Input: adjList = [[2,4],[1,3],[2,4],[1,3]].
  Note: Although examples show adjList, the actual parameter is node. adjList is just a serialized representation of the graph used for input/output display. LeetCode converts adjList -> Node graph before calling our function, and converts our cloned graph back to adjList to verify.

Method

Key Approach - BFS + Hashmap

• Use a hashmap to map each original node to its cloned node
• BFS through the graph:
  • For each neighbor:
    • If not cloned, clone it and push to queue
    • Add the cloned neighbor to the current cloned node’s neighbors list

Edge Case

• if no root, return None
• cycle, use hashmap as visited

Complexity

• Time Complexity: O(V + E)
  • Visit each node once, and traverse each edge once
• Space Complexity: O(V)

Code

from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return None
 
        dic = {node: Node(node.val)}
 
        queue = deque()
        queue.append(node)
        while queue:
            cur = queue.popleft()
            for nei in cur.neighbors:
                if nei not in dic:
                    dic[nei] = Node(nei.val)
                    queue.append(nei)
                dic[cur].neighbors.append(dic[nei])
                
        return dic[node]

---

History

• Feb-15-2026 peeked
  • if nei not in hashmap, create its clone and pushnei
  • always connect
  • No visited needed
• Jan-15-2026 peeked with strong hint (redo)