Clone Graph

Difficulty: Medium

Problem

You are given a reference to one node of a connected undirected graph. Each node carries a value and a list of its neighbor NODES — actual object references, not indices. Return a DEEP COPY of the graph: brand-new node objects, wired to each other exactly like the originals, sharing nothing with the original graph. For input and output, the graph is serialized as an adjacency list where index i holds the neighbor values of node i+1.

Example

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: The graph is a square: 1-2-3-4-1. The copy serializes to the identical adjacency list — same shape, same values — but every node object in it is brand new. Modify the copy and the original doesn't feel a thing.

Brute-force approach

No brute-force phase here — without the old→new map, every attempt breaks on shared neighbors and cycles. The map IS the algorithm.

Optimal approach

Key insight: One map answers both dangerous questions: 'did I already clone this node?' and 'where is its clone?'. Create each clone exactly once; wire every edge to clones only.

BFS over the ORIGINAL graph while an old→new map builds the copy on the side: clone each node the first time it's seen, and recreate every edge between clones only.

Steps

  1. Null guard: an empty graph clones to null
  2. Seed the map with the entry node's clone; start BFS from the ORIGINAL node
  3. Pop an original; for each neighbor not yet in the map, create its clone and enqueue the original
  4. Always wire clones[cur] → clones[nb] — every edge, copies only
  5. Return clones[node], the entry point of the new graph

Time complexity: O(V + E) · Space complexity: O(V)