Q81: Clone Graph. - DSA Patterns (Multi-Lang)

In Simple Words: DFS with a Hash Map mapping originalNode -> clonedNode. If node already in map, return clone; else create clone, add to map, and recursively clone each neighbor.

Time: $O(V + E)$ | Space: $O(V)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

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

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