A connected undirected graph of n nodes labeled 1..n is given as an adjacency list: adjList[i] holds the labels adjacent to node i+1. Build the graph as linked node objects, DEEP-COPY it — new node objects, same structure — and return the CLONE's adjacency list, each neighbour list sorted ascending. Honesty note: the interview version hands you a node and checks that the returned structure shares no objects with the original. A value comparison cannot see object identity, so here the discipline is yours to keep; the coaching walks through why a visited-map is what prevents both infinite loops and accidental sharing.
Examples
Example 1:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Example 2:
Input: adjList = [[]]
Output: [[]]
Explanation: one node, no edges.
Example 3:
Input: adjList = []
Output: []
Example 4:
Input: adjList = [[2],[1]]
Output: [[2],[1]]
Constraints
0 <= n <= 100
The graph is connected and undirected: j in adjList[i] implies i+1 in adjList[j-1]. No self-loops.
Prerequisites
Graph traversal — DFS and BFS, and a visited set as the thing that makes both terminate. Union-find for connectivity questions; topological order for dependency ones.
How to think about it
1. A Map From Original to Copy Optimal
Intuition
Copying a graph means copying nodes AND rewiring their neighbours to the copies — and cycles make that dangerous, because following neighbours blindly recurses forever. One map from original node to its copy solves both problems at once: it is the memo that terminates the recursion, and it guarantees each original maps to exactly one copy, so no copy accidentally points back into the original graph. Saying that the map does two jobs is the interview answer.
Algorithm
1. Build the graph from the adjacency list. 2. DFS from a node; if it is already in the map, return its copy. 3. Otherwise create the copy, record it BEFORE recursing, then copy each neighbour. 4. Serialise the copies back to an adjacency list.
Time & Space
Time O(nodes + edges). Space O(nodes) for the map.