Clone Graph medium

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 val (int) and a list of its neighbors (Node[]).

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

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. Node 1's neighbors are node 2 and node 4. Node 2's neighbors are node 1 and node 3. Node 3's neighbors are node 2 and node 4. Node 4's neighbors are node 1 and node 3.

Example 2

Input: adjList = [[]] Output: [[]] Explanation: Node 0 does not have any neighbors.

Steps

1. Map Old Nodes to New Nodes: Create a HashMap (or unordered_map in C++) to store the mapping between nodes in the original graph and their corresponding clones in the new graph. This prevents infinite recursion and ensures that each node is cloned only once.

2. Depth-First Search (DFS) or Breadth-First Search (BFS): Use a DFS or BFS traversal to explore the graph. For each node encountered:

   • If the node is already in the HashMap, return its clone (avoiding redundant cloning).
   • Otherwise, create a new node with the same val as the original node.
   • Add this new node to the HashMap.
   • Recursively (DFS) or iteratively (BFS) clone the neighbors of the current node and add them to the neighbors list of the newly created node.

3. Return the Clone of the Root Node: After the traversal is complete, return the cloned node that corresponds to the original root node.

Explanation

The key to solving this problem efficiently is avoiding infinite recursion and redundant cloning. The HashMap serves as a memoization table, storing already cloned nodes and their corresponding original nodes. This ensures that when a node is visited multiple times, we don't create multiple clones of it. The DFS (or BFS) ensures that we visit all the nodes and their neighbors in a systematic manner to create a complete copy of the graph.

Code

#include <iostream>
#include <vector>
#include <unordered_map>

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

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (node == nullptr) return nullptr;

        std::unordered_map<Node*, Node*> nodeMap;
        return clone(node, nodeMap);
    }

private:
    Node* clone(Node* node, std::unordered_map<Node*, Node*>& nodeMap) {
        if (nodeMap.count(node)) return nodeMap[node]; // Already cloned

        Node* cloneNode = new Node(node->val);
        nodeMap[node] = cloneNode; // Add to map

        for (Node* neighbor : node->neighbors) {
            cloneNode->neighbors.push_back(clone(neighbor, nodeMap));
        }

        return cloneNode;
    }
};

Complexity

• Time Complexity: O(N + M), where N is the number of nodes and M is the number of edges. We visit each node and edge once.
• Space Complexity: O(N), where N is the number of nodes. The space is used primarily by the HashMap to store the mapping between nodes and their clones, and the recursion stack (in the case of DFS). For BFS, the queue adds a minor space overhead but doesn't change the overall asymptotic complexity.