DSA problem
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. The graph is represented as an adjacency list, and is guaranteed to be connected (every node is reachable from the given reference). For a node with value v, all clones should preserve the SAME neighbor structure as the originals.
The challenge is twofold. First, the graph may contain cycles, so a naive DFS that blindly recurses into neighbors would loop forever. Second, two original nodes that point to the SAME neighbor must point to the SAME cloned neighbor — duplicating the same node twice would produce a wrong, structurally different graph.
Both problems are solved by a single hashmap from original-node to clone-node. Whenever DFS is about to clone a node, it first checks the map: if the clone already exists, return it; otherwise create the clone, INSERT it into the map BEFORE recursing into its neighbors (this is critical to break cycles), and then attach cloned neighbors one by one.
The result is a clean O(N + E) DFS where N is the number of nodes and E is the number of edges. Each node is cloned exactly once, and each edge is traversed twice (once from each endpoint) because the graph is undirected. Recursion depth is bounded by N, giving O(N) auxiliary space.
Examples
adjList = [[2,4],[1,3],[2,4],[1,3]][[2,4],[1,3],[2,4],[1,3]]adjList = [[]][[]]adjList = [][]Constraints
- The number of nodes in the graph is in the range [0, 100].
- 1 <= Node.val <= 100
- Node.val is unique for each node.
- There are no repeated edges and no self-loops in the graph.
- The graph is connected and all nodes can be visited starting from the given node.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.