algoadvance

Leetcode Problem 133: Clone Graph

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 of its neighbors.

class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

Clarifying Questions

  1. Q: Is it possible to have nodes with the same value in the graph? A: Yes, node values are not guaranteed to be unique.

  2. Q: Is the graph always connected? A: Yes, as stated in the problem.

  3. Q: Can the input node be None? A: Yes, the input can be None and in that case, the output should also be None.

  4. Q: What is the range of node values and the maximum number of nodes? A: Node values are typically positive integers. The graph can have up to 100 nodes.

Strategy

  1. Use DFS/BFS Traversal: To clone the graph, we can perform a depth-first search (DFS) or breadth-first search (BFS) traversal.

  2. HashMap to Track Clones: Utilize a hashmap (dictionary) to store the mapping from original nodes to their clone nodes to avoid duplication.

  3. Recursive/Iterative Approach: Both recursive (DFS) and iterative (BFS) approaches can be used. We’ll demonstrate the BFS approach using a queue for simplicity.

Code

The following code uses BFS to clone the graph:

from collections import deque

class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node: 'Node') -> 'Node':
    if not node:
        return None

    # Dictionary to store the mapping from original node to its clone
    clone_map = {node: Node(node.val)}

    # Initialize BFS queue
    queue = deque([node])

    while queue:
        current_node = queue.popleft()

        # Iterate over all the neighbors of the current node
        for neighbor in current_node.neighbors:
            if neighbor not in clone_map:
                # Clone the neighbor and add it to the dictionary
                clone_map[neighbor] = Node(neighbor.val)
                # Enqueue the original neighbor node
                queue.append(neighbor)
            # Add the clone of the neighbor to the cloned node's neighbors list
            clone_map[current_node].neighbors.append(clone_map[neighbor])

    # Return the clone of the start node
    return clone_map[node]

Time Complexity

Try our interview co-pilot at AlgoAdvance.com