Clone Graph 🧠

LeetCode Link: Clone Graph

Difficulty: Medium

Problem Explanation 📝

Problem: LeetCode 133 - Clone Graph

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.

Intuition: To clone a graph, we can use a depth-first search (DFS) or breadth-first search (BFS) approach. The idea is to traverse the original graph and create a copy of each node and its neighbors. We can store the visited nodes in a map to ensure that we don't create duplicate copies.

Approach:

1. Define a helper function cloneNode:

• Create a copy of the current node.
• Iterate through the neighbors of the current node:
• If a neighbor is not visited, recursively call cloneNode to create a copy of the neighbor and add it to the neighbors of the current node.
• If a neighbor is already visited, add the corresponding copy from the map to the neighbors of the current node.

2. Create an empty map to store the copies of the nodes.
3. Call the cloneNode function with the given reference node.
4. Return the copy of the reference node.

⌛ Time Complexity: The time complexity is O(V + E), where V is the number of nodes (vertices) and E is the number of edges in the graph. We visit each node and each edge once.

💾 Space Complexity: The space complexity is O(V), where V is the number of nodes (vertices) in the graph. This is the space used to store the copies of the nodes and the recursion stack.

Solutions 💡

Cpp 💻

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

        unordered_map<Node *, Node *> nodeMap; // Map to store copies of nodes
        return cloneNode(node, nodeMap);
    }

  private:
    Node *cloneNode(Node *node, unordered_map<Node *, Node *> &nodeMap) {
        // If a copy of the current node already exists, return it
        if (nodeMap.find(node) != nodeMap.end()) {
            return nodeMap[node];
        }

        Node *newNode = new Node(node->val);  // Create a new copy of the current node
        nodeMap[node] = newNode;  // Add the current node to the map

        // Recursively clone the neighbors of the current node
        for (Node *neighbor : node->neighbors) {
            newNode->neighbors.push_back(cloneNode(neighbor, nodeMap));
        }

        return newNode;
    }
};

Python 🐍

"""
# Definition for a Node.
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

        visited = {}  # Dictionary to store the cloned nodes

        def dfs(original_node):
            if original_node in visited:
                return visited[original_node]

            new_node = Node(original_node.val)
            visited[original_node] = new_node

            for neighbor in original_node.neighbors:
                new_neighbor = dfs(neighbor)
                new_node.neighbors.append(new_neighbor)

            return new_node

        return dfs(node)