121. Clone Graph

Traverse the adjacency list using recursive DFS. Build the cloned adjacency list node by node, using a visited set to avoid revisiting.

Brute Force

Perform a DFS from node 1. For each node visited, copy its neighbor list into the result. Use a visited set to avoid infinite loops in the undirected graph.

This is effectively the same complexity as BFS but uses recursion. Time is O(V + E) and space is O(V) for the visited set plus O(V) recursion stack.

Note: For an adjacency list representation, DFS and BFS are both O(V + E). The "brute" label here reflects that DFS with recursion is the more straightforward first approach.

import java.util.*;

class Solution {
    public List<List<Integer>> cloneGraph(List<List<Integer>> adjList) {
        if (adjList == null || adjList.isEmpty()) return new ArrayList<>();
        int n = adjList.size();
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < n; i++) result.add(new ArrayList<>());
        boolean[] visited = new boolean[n];
        dfs(0, adjList, result, visited);
        return result;
    }

    private void dfs(int u, List<List<Integer>> adjList, List<List<Integer>> result, boolean[] visited) {
        if (visited[u]) return;
        visited[u] = true;
        result.set(u, new ArrayList<>(adjList.get(u)));
        for (int v : adjList.get(u)) {
            dfs(v - 1, adjList, result, visited);
        }
    }
}

Use BFS with a hash map to track which nodes have been cloned. Process each node level by level, copying its neighbors. The hash map maps old node indices to their cloned neighbor lists.

Mental Model

Think of cloning as visiting every room in a building and making a blueprint. BFS explores the building level by level, and a hash map ensures we never draw the same room twice. When we encounter a neighbor, we either retrieve its already-drawn copy or create a new blank room for it.

Algorithm Steps

1. If the adjacency list is empty, return [].
2. Create a result adjacency list of the same size, initialized with empty lists.
3. Create a visited set and a queue starting with node 0 (index 0 = node 1).
4. While the queue is not empty: a. Dequeue node index u. b. Copy the neighbor list: result[u] = list(adjList[u]). c. For each neighbor v (converted to 0-indexed), if v not in visited, mark it visited and enqueue it.
5. Return the result.

Worked Walk-through

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

result = [[2,4],[1,3],[2,4],[1,3]] -- identical structure to input.

Edge Cases

• Empty graph: adjList = []. Return [].
• Single node, no edges: adjList = [[]]. Return [[]].
• Fully connected: every node connects to every other. BFS still visits each node once.

Complexity

• Time: O(V + E) -- each node dequeued once, each edge examined once.
• Space: O(V) -- visited set and queue hold at most V nodes.