[Top Interview 150] 133. Clone Graph

Solution)

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        # Base Case
        if not node: return

        # Dict that will save {original nodes : copied nodes}
        # It's used to check if we've already created a certain node
        oldToNew = {}

        # Recursively copy nodes and connect them as neighbors
        def dfs(node):
            # Checking if the current node is already copied 
            if node in oldToNew:
                return oldToNew[node]

            # Copy the curr node and save the nodes in a dictionary
            copy = Node(node.val)
            oldToNew[node] = copy

            # Connect neighbors
            for nei in node.neighbors:
                copy.neighbors.append(dfs(nei))

            # Return a copied 1-indexed node
            return copy
    
        return dfs(node)

 
Problem: LeetCode
Reference: NeetCode
 
Time Complexity: O(n+e)
Space Complexity: O(n)
*n = number of nodes, e = number of edges
 

Explanation)

We'll use DFS to clone and connect the nodes.
 
The logic behind DFS is to save the original and copied nodes that were visited in a dictionary.
 
Then to connect the neighboring nodes, we'll check if the neighboring nodes are already visited.
1) If visited, we simply append that neighboring node to the attribute neighbors
2) If not visited, we need to repeat the step above (copying and saving nodes). Once we copy the node, we repeat the process of matching the neighboring nodes.
 

1. Base Case & Initialization)

If the graph is empty, return None.
 
Variable oldToNew is a dict that will save {original nodes : copied nodes}. We'll use this dictionary to check if the current is visited or not.
 

def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        # 1. Base Case & Initialization
        if not node: return

        oldToNew = {}

 

2. Check if node is visited)

We'll implement a helper function.
 
This helper function dfs() will copy and save nodes in oldToNew. Then as we DFS, we'll connect neighboring nodes if they have been already created.
 
To connect existing neighboring nodes, it's necessary for us to see if node is in oldToNew. If it does already exist, we'll return the copied version of it.
 
The returned copied node will then be saved in the attribute neighbors in following steps.
 

def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        # 1. Base Case & Initialization
        if not node: return

        oldToNew = {}
        
        def dfs(node):
            # 2. Check if node is visited
            if node in oldToNew:
                return oldToNew[node]

 

3. Copy and save the current node)

If the current node hasn't been created yet, we then need to copy the current node.
 
Make sure to save the copied node in oldToNew.
 

def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        # 1. Base Case & Initialization
        if not node: return

        oldToNew = {}
        
        def dfs(node):
            # 2. Check if node is visited
            if node in oldToNew:
                return oldToNew[node]

            # 3. Copy and save the current node
            copy = Node(node.val)
            oldToNew[node] = copy

 

4. Connect the neighboring nodes)

Once we've created new nodes, we need to save the neighboring nodes to the new node's attribute neighbors.
 
We'll do that by appending dfs(neighboring nodes). Now there are two outcomes in this recursion.
1) If the neighboring nodes are already in oldToNew, we simply append the copied nodes that are saved in oldToNew. This is shown in Step 2.
2) If they haven't been created yet, there's no way for us to connect a non-existing node. Thus we need to copy that neighboring nodes. This is shown in Step 3.
 
This is a DFS recursion. Once all the nodes are copied and proper neighbors are connected, we return the 1-indexed copied node.
 

def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        # 1. Base Case & Initialization
        if not node: return

        oldToNew = {}
        
        def dfs(node):
            # 2. Check if node is visited
            if node in oldToNew:
                return oldToNew[node]

            # 3. Copy and save the current node
            copy = Node(node.val)
            oldToNew[node] = copy

            # 4. Connect the neighboring nodes
            for nei in node.neighbors:
                copy.neighbors.append(dfs(nei))

            return copy
    
        return dfs(node)

 
 
 
This was a new type of algorithm/problem which was hard to understand. I also haven't been doing LeetCode during Chuseok, so it took me a while for my brain to start coding.