Coding Interview Questions | Clone Graph

January 12th, 2024

Clone Graph Problem Introduction:

This summary will talk about my solution to the clone graph problem as seen on leetcode here.

How do you solve the Clone Graph Problem using Depth-First-Search?

Solution:

function cloneGraph(node: Node | null): Node | null {
  if (!node) {
    return null;
  }
  const newNode = new Node(node.val);
  const nodesVisitedMap = new Map<number, Node>();
  const nodeStack = [node];
  nodesVisitedMap.set(newNode.val, newNode);

  while (nodeStack.length > 0) {
    const currentNode = nodeStack.pop()!;

    for (const neighbor of currentNode.neighbors) {
      const newNeighbor = new Node(neighbor.val);
      if (!nodesVisitedMap.has(neighbor.val)) {
        nodesVisitedMap.set(neighbor.val, newNeighbor);
        nodeStack.push(neighbor);
      }
      // Update neighbor values for copy of node
      nodesVisitedMap
        .get(currentNode.val)!
        .neighbors.push(nodesVisitedMap.get(neighbor.val)!);
    }
  }

  return newNode;
}

Clone Graph Solution Summary:

Below is a breakdown of the key aspects of the solution above:

Node Creation and Initialization: The algorithm initializes a new node (newNode) with the value of the input node (node). It also uses a stack (nodeStack) for iterative depth-first traversal and a map (nodesVisitedMap) to keep track of visited nodes during the traversal.
```
const newNode = new Node(node.val);
const nodesVisitedMap = new Map<number, Node>();
const nodeStack = [node];
nodesVisitedMap.set(newNode.val, newNode);
```

Depth-First Traversal and Cloning: The solution utilizes an iterative depth-first traversal using a stack. It pops nodes from the stack, creates new nodes for each neighbor if not visited before, and updates the neighbors of the current node in the cloned graph.

while (nodeStack.length > 0) {
  const currentNode = nodeStack.pop()!;
  for (const neighbor of currentNode.neighbors) {
    const newNeighbor = new Node(neighbor.val);
    if (!nodesVisitedMap.has(neighbor.val)) {
      nodesVisitedMap.set(neighbor.val, newNeighbor);
      nodeStack.push(neighbor);
    }
    nodesVisitedMap
      .get(currentNode.val)!
      .neighbors.push(nodesVisitedMap.get(neighbor.val)!);
  }
}

Complexities:

Time Complexity: The time complexity is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. This is because each node and edge are visited once during the depth-first traversal.
Space Complexity: The space complexity is O(V), where V is the number of vertices. The space is primarily used for storing the cloned nodes in the nodesVisitedMap and the traversal stack.