Clone Graph LeetCode 133

Question

I working on Leetcode 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 (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

I've been struggling with this for quite a long time. My solution:

 /**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function (node) {
  if (!node) {
    return node;
  }
  const nodeCopy = new Node(node.val);
  let stack = [node];
  let nodeMap = {};
  nodeMap[node.val] = nodeCopy;
  while (stack.length > 0) {
    const currentNode = stack.shift();
    const currentNodeCopy = nodeMap[currentNode.val];
    let nodeNeighbors = currentNode.neighbors;
    while (nodeNeighbors.length > 0) {
      const currentNeighbor = nodeNeighbors.shift();
      let existingNeighborCopy = nodeMap[currentNeighbor.val];
      // console.log(existingNeighborCopy);
      if (!existingNeighborCopy) {
        stack.push(currentNeighbor);
        nodeMap[currentNeighbor.val] = new Node(currentNeighbor.val);
      }
      // console.log('Existing Neighbor');
      // Already Visited;
      currentNodeCopy.neighbors.push(nodeMap[currentNeighbor.val]);
    }
  }
  console.log(nodeCopy);
  console.log(nodeCopy.neighbors[0]);
  return nodeMap[node.val];
};

It does DFS iteratively. But for the base test case given:

[[2,4],[1,3],[2,4],[1,3]]

It throws the output:

Node with value 2 doesn't exist in the original graph.

Which seems plain wrong, since there is a node with 2 value. What could be the issue in the above code?

Answer 1

This happens because you mutate the input graph by doing:

nodeNeighbors.shift();

Apparently, the LeetCode test code does not maintain its own copy of the input graph, so when it runs your code and tries to compare the input graph with the returned graph, it finds that in the input graph node 1 has no neighbors and thus it says there is no node 2.

So don't mutate the input graph, and change the following two lines:

    while (nodeNeighbors.length > 0) {
      const currentNeighbor = nodeNeighbors.shift();

...to:

    for (const currentNeighbor of nodeNeighbors) {

Another implementation

You could consider using recursion instead of using an explicit stack.

var cloneGraph = function(node) {
    if (!node) return null;
    const nodeMap = [0];

    const dfs = ({ val, neighbors }) =>
        Object.assign(nodeMap[val] = new Node(val), {
            neighbors: neighbors.map(neighbor =>
                nodeMap[neighbor.val] ?? dfs(neighbor)
            )
        });

    return dfs(node);
};

Answer 2

Adding a solution in java for the same with better T, S complexity.

class Solution {
    // O(N)time
    // O(N)space
    HashMap<Integer, Node> graphDataMap = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null)
            return node;
        depthFirstSearch(node);
        return graphDataMap.get(node.val);
    }

    void depthFirstSearch(Node node) {
        if (graphDataMap.containsKey(node.val)) {
            return;
        }
        Node cloneNode = new Node(node.val);
        graphDataMap.put(node.val, cloneNode);
        for (Node n : node.neighbors) {
            depthFirstSearch(n);
            cloneNode.neighbors.add(graphDataMap.get(n.val));
        }
    }
}
```