LT #133: Clone Graph

Day: 2
Type: Graphs
Level: Easy
Link: https://leetcode.com/problems/clone-graph/description/

TL:DR

Algorithm: BFS/DFS
Approach: Run BFS with the start node. Connect the old node value with new node value — along with connections. HashMap keeps track of the old nodes and new cloned nodes. For each current node in BFS, go through it’s neighbors and map those too (if they haven’t been accessed yet). After adding, connect the neighbors.

Solving the problem

1. Thinking about the problem, it seems like we need to make an exact copy of the current graph (values as well as their connections). So we need to iterate over all nodes — the method that needs to be defined takes in the start node.
2. Data structure for storing the nodes: HashMap where key = node from old graph, value = node from new graph. The hashmap will also keep track of the connected nodes (neighbors).

clonedNodes = {} # defining hashmap

3. Defining BFS — similar what we have done in previous problems

def bfs(node):
            q = deque() # defining the queue to store nodes that are being iterated
            q.append(node) # add node in queue
            
            # create new node and assign the node to the new node with same value
            # At this point - neighbors have not been assigned yet
            clonedNodes[node] = Node(node.val) 
            
            while q:
                current = q.popleft() # pop based on FIFO
                for neighbor in current.neighbors:
                    if neighbor not in clonedNodes:
                        # create new node and assign value same as current neighbor node
                        # Map this new node to old neighbor
                        clonedNodes[neighbor] = Node(neighbor.val)
                        q.append(neighbor)
                    
                    # this step will set neighbors of the new current node
                    clonedNodes[current].neighbors.append(clonedNodes[neighbor])

bfs(node) # run bfs with the first node
return clonedNodes[node] # return hashmap with the first node

Ananlysis

Space Complexity: total space complexity is O(V + E), where V is the number of vertices (nodes) and E is the number of edges.

Time Complexity: total time complexity is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph.