Clone Graph

• Difficulty: Medium
• Topics: Hash Table, Depth-First Search, Breadth-First Search, Graph
• Link: https://leetcode.com/problems/clone-graph/

Problem Description

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.

class Node {
    public int val;
    public List<Node> neighbors;
}

Test case format:

For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.

Constraints:

• The number of nodes in the graph is in the range [0, 100].
• 1 <= Node.val <= 100
• Node.val is unique for each node.
• There are no repeated edges and no self-loops in the graph.
• The Graph is connected and all nodes can be visited starting from the given node.

Solution

1. Problem Deconstruction

Technical Restatement
Given a connected undirected graph represented by node objects containing unique integer values and adjacency lists, create a deep copy where:

• Every node is instantiated anew
• All neighbor relationships are preserved without shared references
• The clone maintains identical topological structure to the original

Beginner-Friendly Explanation
Imagine you have a spider web where each intersection (node) is connected by threads (edges) to others. Your task is to create an exact replica of this web using new materials. Each copied intersection must connect only to other copied intersections in precisely the same pattern.

Mathematical Formulation
Let $G = (V, E)$ be a graph with vertex set $V$ and edge set $E$. For each $v \in V$, create $v'$ such that:

$$\forall v \in V, \exists! v' \notin V$$

$$E' = \{ (v'_i, v'_j) \mid (v_i, v_j) \in E \}$$

Return $v'_1$ (clone of the first node) as the entry point to $G' = (V', E')$.

Constraint Analysis

1. 0 ≤ Nodes ≤ 100:
   • Allows O(n²) algorithms but encourages O(n) approaches
   • Edge case: Empty input (return null) must be explicitly handled
2. Unique Node Values:
   • Enables value-based lookups (though object references are safer)
   • Implies no two nodes share the same adjacency list signature
3. No Cycles/Self-Edges:
   • Eliminates need for cycle-specific edge cases during traversal
   • Ensures neighbor lists are strictly other nodes
4. Connected Graph:
   • Guarantees full traversal from the starting node
   • Prevents disconnected components from being missed

---

2. Intuition Scaffolding

Analogies

1. Real-World: Copying a corporate hierarchy chart. Each employee (node) has direct reports (neighbors). Photocopying the chart requires new paper sheets (node instances) with identical reporting lines.
2. Gaming: Duplicating a dungeon map in a RPG. Each room (node) connects to others via doors. The clone must have new room instances with matching door connections.
3. Math: Constructing a graph isomorphism φ: V → V’ where adjacency is preserved:

   $$(u, v) \in E \iff (φ(u), φ(v)) \in E'$$

Common Pitfalls

1. Shallow Copy Neighbors: Copying neighbor references instead of creating new nodes.
2. Infinite Loops: Not tracking visited nodes when graphs have cycles.
3. Null Handling: Missing base case when input graph is empty.
4. Assumption of Sorted Neighbors: Incorrectly relying on neighbor order for correctness.
5. Value-Based Lookups: Using node values as keys in maps (risky if values aren’t unique).

---

3. Approach Encyclopedia

Brute Force (Infeasible)

• Idea: For each node, create a copy and recursively copy all neighbors.
• Flaw: Exponential duplication (multiple copies of same node) → O(nⁿ) time.

Breadth-First Search (Optimal)

• Pseudocode:

  from collections import deque  
  
  def cloneGraph(node):  
      if not node: return None  
      clones = {node: Node(node.val)}  # Original → Clone mapping  
      q = deque([node])  
      while q:  
          curr = q.popleft()  
          for neighbor in curr.neighbors:  
              if neighbor not in clones:  
                  clones[neighbor] = Node(neighbor.val)  
                  q.append(neighbor)  
              clones[curr].neighbors.append(clones[neighbor])  
      return clones[node]  
  

• Complexity:
  • Time: O(V + E) → Each node and edge processed exactly once.
  • Space: O(V) → Queue and map store all nodes.
• Visualization:

  Original: 1───2     Clone: 1'───2'  
            │   │            │   │  
            4───3            4'───3'  
  BFS Queue: [1] → [2,4] → [4,3] → [3] → []  
  Clones Map: {1:1'} → {1:1', 2:2'} → ...  
  

Depth-First Search (Optimal)

• Pseudocode:

  def cloneGraph(node):  
      clones = {}  
      def dfs(original):  
          if not original: return None  
          if original in clones:  
              return clones[original]  
          clone = Node(original.val)  
          clones[original] = clone  
          for neighbor in original.neighbors:  
              clone.neighbors.append(dfs(neighbor))  
          return clone  
      return dfs(node)  
  

• Complexity: Same as BFS but uses implicit call stack.

---

4. Code Deep Dive

BFS Solution Line-by-Line

from collections import deque  

def cloneGraph(node):  
    if not node:  # Edge Case: Empty input  
        return None  
    clones = {node: Node(node.val)}  # Init map with first node  
    q = deque([node])  # Start BFS from original node  
    while q:  
        curr = q.popleft()  
        for neighbor in curr.neighbors:  # Process all connections  
            if neighbor not in clones:  
                clones[neighbor] = Node(neighbor.val)  # Clone missing node  
                q.append(neighbor)  # Schedule for BFS expansion  
            clones[curr].neighbors.append(clones[neighbor])  # Link clones  
    return clones[node]  # Return clone of input node  

Edge Case Handling

• Example 2 (Single Node): node.val=1, neighbors empty. Loop skips (no neighbors), returns clone with empty list.
• Example 3 (Empty Input): Function returns None immediately.
• Cyclic Graph: Nodes re-encountered via neighbors are found in clones, preventing loops.

---

5. Complexity War Room

Hardware Considerations

• At 100 nodes, the BFS queue uses ≈ 400 bytes (4 bytes per reference × 100). Fits in CPU cache.
• DFS recursion depth ≤ 100 → Safe (Python default recursion limit is 1000).

Approach Comparison

Approach	Time	Space	Readability	Interview Viability
BFS	O(V+E)	O(V)	High	✅ Preferred
DFS	O(V+E)	O(V)	High	✅
Brute	O(nⁿ)	O(1)	Low	❌

---

6. Pro Mode Extras

Variants

1. Directed Graph: Same approach works (edges are unidirectional).
2. Weighted Edges: Add weight attribute to edges during cloning.
3. Disconnected Graph: Iterate all nodes and clone components (problem states graph is connected).

Interview Cheat Sheet

• Key Insight: Use a hash map to track clones and avoid cycles.
• Verbally Confirm: “I assume node values are unique per constraints.”
• Test Case: Always test single-node and two-node cyclic graphs.