133. Clone Graph

At a Glance

• Topic: Hash Table
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 133

Problem Statement

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 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.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

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 no...

Approach & Solution Steps

• BFS queue — clone nodes as discovered — O(V+E).
• Optimal — DFS memo map — same complexity, natural recursion.

Optimal JS Solution

function cloneGraph(node) {
  if (!node) {
    return null;
  }
  const visited = new Map();

  function dfs(source) {
    if (visited.has(source)) {
      return visited.get(source);
    }
    const copy = { val: source.val, neighbors: [] };
    visited.set(source, copy);
    for (const neighbor of source.neighbors) {
      copy.neighbors.push(dfs(neighbor));
    }
    return copy;
  }

  return dfs(node);
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.