LeetCode Solution 133 - Clone Graph

Problem Statement

You are given a reference of a node in a connected, undirected graph. Each node has a unique value and a list of neighbors. Your task is to return a deep copy (clone) of the graph.

Each node is defined as:

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

Constraints:

• The number of nodes in the graph is in the range [0, 100].
• Node.val is unique for each node.
• The graph is connected.

---

Optimal Approach - DFS (Depth First Search)

To clone the graph, we use DFS with a hashmap to keep track of cloned nodes.

Explanation:

1. Use a hashmap (unordered_map<int, Node*>) to store the mapping between original and cloned nodes.
2. Recursively traverse each node and its neighbors.
3. If a node is already cloned, return the clone.
4. Otherwise, create a new node, store it in the hashmap, and clone its neighbors recursively.

C++ Code (LeetCode-Compatible)

class Solution {
public:
    unordered_map<Node*, Node*> cloneMap;
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        
        if (cloneMap.find(node) != cloneMap.end())
            return cloneMap[node];
        
        Node* clone = new Node(node->val);
        cloneMap[node] = clone;
        
        for (Node* neighbor : node->neighbors)
            clone->neighbors.push_back(cloneGraph(neighbor));
        
        return clone;
    }
};

---

Step-by-Step Explanation

1. Base Case: If node == nullptr, return nullptr.
2. Check in HashMap: If node already exists in cloneMap, return the clone.
3. Clone the Node: Create a new node and store it in the hashmap.
4. Clone Neighbors: Recursively clone all neighbors and add them to the new node’s neighbors list.
5. Return the Cloned Node.

---

Dry Run / Execution Steps

Example:

Input:
    1 -- 2
    |    |
    4 -- 3

Step-by-step cloning:

Original Node	Action
1	Create clone 1, recurse into neighbors
2	Create clone 2, recurse into neighbors
3	Create clone 3, recurse into neighbors
4	Create clone 4, recurse into neighbors

Output: A cloned graph with the same structure.

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Without HashMap)	O(N^2)	O(N)	Leads to redundant cloning
BFS (Iterative)	O(N)	O(N)	Same time as DFS, just iterative
DFS (Best)	O(N)	O(N)	Simple & efficient

---

Best Solution & Why It’s Best

The DFS with HashMap approach is the best because:

1. Linear Time Complexity O(N), since each node is visited once.
2. Constant Extra Space O(N), only storing nodes in the hashmap.
3. Avoids Redundant Cloning, ensuring an efficient deep copy.

---

Complexity Analysis

• Time Complexity: O(N), as each node and edge is processed once.
• Space Complexity: O(N), for storing clones in the hashmap.

---

Conclusion

• The best approach is DFS with HashMap.
• BFS can be used as an alternative but has the same complexity.
• Recommended practice problems:
  • Copy List with Random Pointer (LeetCode 138)
  • Graph Valid Tree (LeetCode 261)
  • Course Schedule (LeetCode 207)