Skip to main content

🟨 Clone Graph (#133)

🔗 Problem Link​

📋 Problem Statement​

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

💡 Examples​

Example 1​

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]

Example 2​

Input: adjList = [[]]
Output: [[]]

🔑 Key Insights & Approach​

Core Observation: Use DFS/BFS with hashmap to track cloned nodes and avoid infinite loops.

Why HashMap?

  • O(N + E) time where N = nodes, E = edges
  • O(N) space for hashmap
  • Prevents re-cloning nodes

Approaches:

  1. DFS with hashmap: O(N + E)
  2. BFS with hashmap: O(N + E)

Pattern: "Graph Cloning" with visited tracking.

🐍 Solution: Python​

Approach: DFS with HashMap​

Time Complexity: O(N + E) | Space Complexity: O(N)

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

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None

        clones = {}  # original -> clone mapping

        def dfs(node):
            if node in clones:
                return clones[node]

            # Create clone
            clone = Node(node.val)
            clones[node] = clone

            # Clone neighbors
            for neighbor in node.neighbors:
                clone.neighbors.append(dfs(neighbor))

            return clone

        return dfs(node)

🔵 Solution: Golang​

Approach: DFS​

Time Complexity: O(N + E) | Space Complexity: O(N)

type Node struct {
    Val int
    Neighbors []*Node
}

func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }

    clones := make(map[*Node]*Node)

    var dfs func(node *Node) *Node
    dfs = func(node *Node) *Node {
        if clone, exists := clones[node]; exists {
            return clone
        }

        clone := &Node{Val: node.Val, Neighbors: []*Node{}}
        clones[node] = clone

        for _, neighbor := range node.Neighbors {
            clone.Neighbors = append(clone.Neighbors, dfs(neighbor))
        }

        return clone
    }

    return dfs(node)
}

📚 References​