June 13, 2024

Computer Science
TypeScript
JavaScript

LeetCode Meditations: Clone Graph

Let's start with the description for 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 (List[Node]) of its neighbors.
class Node {
   public int val;
   public List<Node> neighbors;
}
class Node {
   public int val;
   public List<Node> neighbors;
}

The description also indicates that the nodes are 1-indexed, and the graph is represented as an adjacency list. Also, we should return the copy of the given node.

For example:

Input: adjList = [[2, 4], [1, 3], [2, 4], [1, 3]]

Output: [[2, 4], [1, 3], [2, 4], [1, 3]]

Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Input: adjList = [[2, 4], [1, 3], [2, 4], [1, 3]]

Output: [[2, 4], [1, 3], [2, 4], [1, 3]]

Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Our constraints are:

The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
Node.val is unique for each node.
There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.

This problem is, in a sense, just a graph traversal problem that happens to have the additional requirement of cloning the graph.

There are two essential ways to traverse a graph as we've seen before: with a depth-first search and a breadth-first search.

Since we shouldn't mess up the connections between the nodes, we can make use of a Map to map the nodes in the original graph to their clones.

Let's first tackle it by using breadth-first search, after taking a deep breath.

With breadth-first search

The first thing to do is initialize our map:

const nodesMap = new Map<_Node, _Node>();

const nodesMap = new Map<_Node, _Node>();

Now, we can create the clone of the node we're given, and map it to its clone:

let cloneNode = new _Node(node.val);
nodesMap.set(node, cloneNode);

let cloneNode = new _Node(node.val);
nodesMap.set(node, cloneNode);

As with many breadth-first search implementations, we can create a queue, which will initially hold the node we're given:

const queue = [node];

const queue = [node];

Now we can do the actual breadth-first search.

While our queue is not empty, we can iterate over the neighbors of the current node that we've dequeued (by using queue.shift()), mapping each one to its clone, and adding it to the queue for further processing. And, the beautiful thing is, we don't have to create a whole new clone and add it to our queue if that node is already in our map (because we have already "visited" it). We only want to do it if it's not in the map:

if (!nodesMap.has(neighbor)) {
  nodesMap.set(neighbor, new _Node(neighbor.val));
  queue.push(neighbor);
}

if (!nodesMap.has(neighbor)) {
  nodesMap.set(neighbor, new _Node(neighbor.val));
  queue.push(neighbor);
}

Once we map the neighbor to its clone and add it to queue, we can now add the newly cloned neighbor to the neighbors of the clone node we're handling:

let cloneNode = nodesMap.get(currentNode!);
let cloneNeighbor = nodesMap.get(neighbor);
cloneNode!.neighbors.push(cloneNeighbor!);

let cloneNode = nodesMap.get(currentNode!);
let cloneNeighbor = nodesMap.get(neighbor);
cloneNode!.neighbors.push(cloneNeighbor!);

The whole process looks like this:

while (queue.length > 0) {
  let currentNode = queue.shift();
  for (const neighbor of currentNode!.neighbors) {
    if (!nodesMap.has(neighbor)) {
      nodesMap.set(neighbor, new _Node(neighbor.val));
      queue.push(neighbor);
    }
    let cloneNode = nodesMap.get(currentNode!);
    let cloneNeighbor = nodesMap.get(neighbor);
    cloneNode!.neighbors.push(cloneNeighbor!);
  }
}

while (queue.length > 0) {
  let currentNode = queue.shift();
  for (const neighbor of currentNode!.neighbors) {
    if (!nodesMap.has(neighbor)) {
      nodesMap.set(neighbor, new _Node(neighbor.val));
      queue.push(neighbor);
    }
    let cloneNode = nodesMap.get(currentNode!);
    let cloneNeighbor = nodesMap.get(neighbor);
    cloneNode!.neighbors.push(cloneNeighbor!);
  }
}

At the end of the function, we can just return the mapped clone of the node that we were given in the first place:

return nodesMap.get(node) as _Node;

return nodesMap.get(node) as _Node;

Note that the return value of a Map object can possibly be undefined, so the TS compiler will warn us with nodesMap.get(node). The return value of our function can be a _Node or null, and we only want to return null when the node we're given is null:

if (node === null) {
  return null;
}

if (node === null) {
  return null;
}

So, we're already handling the case where node can be null, and when we retrieve its mapped value from nodesMap, we're confident that it will be a _Node, so we're using a type assertion.

Finally, the cloneGraph function looks like this:

/**
 * Definition for _Node.
 * class _Node {
 *   val: number
 *   neighbors: _Node[]
 * 
 *   constructor(val?: number, neighbors?: _Node[]) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.neighbors = (neighbors === undefined ? [] : neighbors)
 *   }
 * }
 * 
 */

function cloneGraph(node: _Node | null): _Node | null {
  if (node === null) {
    return null;
  }

  const nodesMap = new Map<_Node, _Node>();
  let cloneNode = new _Node(node.val);
  nodesMap.set(node, cloneNode);

  const queue = [node];

  while (queue.length > 0) {
    let currentNode = queue.shift();
    for (const neighbor of currentNode!.neighbors) {
      if (!nodesMap.has(neighbor)) {
        nodesMap.set(neighbor, new _Node(neighbor.val));
        queue.push(neighbor);
      }
      let cloneNode = nodesMap.get(currentNode!);
      let cloneNeighbor = nodesMap.get(neighbor);
      cloneNode!.neighbors.push(cloneNeighbor!);
    }
  }

  return nodesMap.get(node) as _Node;
}

/**
 * Definition for _Node.
 * class _Node {
 *   val: number
 *   neighbors: _Node[]
 * 
 *   constructor(val?: number, neighbors?: _Node[]) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.neighbors = (neighbors === undefined ? [] : neighbors)
 *   }
 * }
 * 
 */

function cloneGraph(node: _Node | null): _Node | null {
  if (node === null) {
    return null;
  }

  const nodesMap = new Map<_Node, _Node>();
  let cloneNode = new _Node(node.val);
  nodesMap.set(node, cloneNode);

  const queue = [node];

  while (queue.length > 0) {
    let currentNode = queue.shift();
    for (const neighbor of currentNode!.neighbors) {
      if (!nodesMap.has(neighbor)) {
        nodesMap.set(neighbor, new _Node(neighbor.val));
        queue.push(neighbor);
      }
      let cloneNode = nodesMap.get(currentNode!);
      let cloneNeighbor = nodesMap.get(neighbor);
      cloneNode!.neighbors.push(cloneNeighbor!);
    }
  }

  return nodesMap.get(node) as _Node;
}

Time and space complexity

The time complexity with this breadth-first search implementation is $O(V+E)$ where $V$ is the number of vertices (nodes), and $E$ is the number of edges, as we're traversing the whole graph.

The storage needs for the cloned nodes and nodesMap will grow linearly as the number of nodes in the graph increases, so the space complexity is $O(n)$ where $n$ is the total number of nodes in the graph.

With depth-first search

We can also use depth-first search to solve this problem, as also shown by NeetCode.

Our nodesMap will also be here to map the nodes to their clones:

const nodesMap = new Map<_Node, _Node>();

const nodesMap = new Map<_Node, _Node>();

The dfs function will be recursive, and as with all recursive functions, the first thing that we should be thinking about is the base case(s). A perhaps obvious one is when the given current node is null — in that case, we can return null:

if (currentNode === null) {
  return null;
}

if (currentNode === null) {
  return null;
}

The whole dfs function will eventually return the cloned graph itself (it will return the cloned node of the node we're given).

So, if the node we're looking at is in our map (that we have "visited" it), we can simply return the cloned version of it:

if (nodesMap.has(currentNode)) {
  return nodesMap.get(currentNode);
}

if (nodesMap.has(currentNode)) {
  return nodesMap.get(currentNode);
}

Otherwise, we can create the clone node and set it in our map accordingly:

let cloneNode = new _Node(currentNode.val);
nodesMap.set(currentNode, cloneNode);

let cloneNode = new _Node(currentNode.val);
nodesMap.set(currentNode, cloneNode);

The only thing left is to add the neighbors of currentNode to the neighbors of cloneNode.

Since dfs will be returning the cloned node of a given node, for each neighbor, we can just get its clone with dfs and add it to cloneNode.neighbors:

for (const neighbor of currentNode.neighbors) {
  cloneNode.neighbors.push(dfs(neighbor)!);
}

for (const neighbor of currentNode.neighbors) {
  cloneNode.neighbors.push(dfs(neighbor)!);
}

The final solution with DFS looks like this:

/**
 * Definition for _Node.
 * class _Node {
 *   val: number
 *   neighbors: _Node[]
 * 
 *   constructor(val?: number, neighbors?: _Node[]) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.neighbors = (neighbors === undefined ? [] : neighbors)
 *   }
 * }
 * 
 */

function dfs(currentNode: _Node | null, nodesMap: Map<_Node, _Node>) {
  if (currentNode === null) {
    return null;
  }

  if (nodesMap.has(currentNode)) {
    return nodesMap.get(currentNode);
  }

  let cloneNode = new _Node(currentNode.val);
  nodesMap.set(currentNode, cloneNode);

  for (const neighbor of currentNode.neighbors) {
    cloneNode.neighbors.push(dfs(neighbor, nodesMap)!);
  }

  return cloneNode;
}

function cloneGraph(node: _Node | null): _Node | null {
  const nodesMap = new Map<_Node, _Node>();

  return dfs(node, nodesMap) as _Node;
}

/**
 * Definition for _Node.
 * class _Node {
 *   val: number
 *   neighbors: _Node[]
 * 
 *   constructor(val?: number, neighbors?: _Node[]) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.neighbors = (neighbors === undefined ? [] : neighbors)
 *   }
 * }
 * 
 */

function dfs(currentNode: _Node | null, nodesMap: Map<_Node, _Node>) {
  if (currentNode === null) {
    return null;
  }

  if (nodesMap.has(currentNode)) {
    return nodesMap.get(currentNode);
  }

  let cloneNode = new _Node(currentNode.val);
  nodesMap.set(currentNode, cloneNode);

  for (const neighbor of currentNode.neighbors) {
    cloneNode.neighbors.push(dfs(neighbor, nodesMap)!);
  }

  return cloneNode;
}

function cloneGraph(node: _Node | null): _Node | null {
  const nodesMap = new Map<_Node, _Node>();

  return dfs(node, nodesMap) as _Node;
}

Time and space complexity

Similar to the BFS version, the time complexity is $O(V + E)$ where $V$ is the number of vertices (nodes), and $E$ is the number of edges. The space complexity will be $O(n)$ as well, where $n$ is the number of nodes as we're keeping nodesMap to store all the nodes.

Next up is the problem called Pacific Atlantic Water Flow. Until then, happy coding.

Eda Eren

LeetCode Meditations: Clone Graph

With breadth-first search

Time and space complexity

With depth-first search

Time and space complexity