LeetCode 133 - Clone Graph

This Medium graph problem asks for a deep copy of a connected undirected graph given a reference to a single starting node. To handle cycles and duplicate visits, I used a hash map to memoize cloned nodes and traversed the structure via DFS recursion.

---

Problem link and explanation

• Problem: 133. Clone Graph
• Summary: Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph containing identical node values and neighbor structures without sharing any node references with the original graph.

Because undirected graphs can contain cycles, an unmemoized traversal will loop infinitely trying to clone visited neighbors. A 1:1 lookup map between original nodes and their cloned counterparts is necessary to guarantee single-pass node creation.

---

Approach

Maintain a cloned dictionary mapping each original Node instance to its corresponding copy.

cloned = {}

def dfs(curr):
    if curr in cloned:
        return cloned[curr]

    copy = Node(curr.val)
    cloned[curr] = copy

    for neighbor in curr.neighbors:
        copy.neighbors.append(dfs(neighbor))

    return copy

1. Base condition: If curr is already present in cloned, return the existing clone cloned[curr] immediately.
2. Clone and register: If curr has not been cloned yet, instantiate copy = Node(curr.val) and register it in cloned[curr] before recursing on neighbors. This registration order prevents infinite recursion when neighboring nodes reference curr back.
3. Populate adjacency list: Iterate over curr.neighbors, recursively calling dfs(neighbor) for each, and append the returned clone to copy.neighbors.

---

Complexity analysis

• Time complexity: O(V + E)
  • Every vertex V and edge E is traversed exactly once.
• Space complexity: O(V)
  • The hash map stores all V vertices, and the recursion call stack reaches at most V frames in the worst case.

---

Implementation code

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional


class Solution:

    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return None

        cloned = {}

        def dfs(curr):
            if curr in cloned:
                return cloned[curr]

            copy = Node(curr.val)
            cloned[curr] = copy

            for neighbor in curr.neighbors:
                copy.neighbors.append(dfs(neighbor))

            return copy

        return dfs(node)

---

Summary and reflection

The key invariant in graph cloning is breaking recursive cycles. Storing the newly created node in the memoization table before recursing into its neighbors guarantees that cyclic references resolve immediately to the cloned node instance rather than triggering unbounded recursion.