Clone Graph
Medium · Graphs
You are given a reference to a node in a connected undirected graph, where each node stores an integer value and a list of its neighboring nodes. Produce a deep copy of the entire graph reachable from that node, meaning every node and every edge must be duplicated as new objects rather than reused. Return the corresponding node in the newly built graph, or an equivalent empty result if the input graph is empty. The graph is represented for testing as an adjacency list where the i-th entry lists the neighbor values of node i+1.
Examples
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Why: Node 1 connects to 2 and 4, node 2 connects to 1 and 3, and so on; the copy must reproduce this exact connection pattern with brand new node objects.Input: adjList = [[]]
Output: [[]]
Why: There is a single node with no neighbors, so the clone is a single isolated node.Input: adjList = []
Output: []
Why: An empty graph has no starting node at all, so the copy is also empty.Constraints
0 <= number of nodes <= 100, 1 <= node.val <= 100, all node values are unique, the graph has no repeated edges or self-loops
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Clone Graph. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.