Clone a graph.
MediumGiven a node in a connected, undirected graph, return a deep copy of the graph. Each node has an integer val and a list of its neighbors.
A deep copy has the same structure as the original, but every node in it is new. No node or neighbor list in the copy can point back into the original graph.
Node values run from 1 to n, and you're given the node with value 1. The examples and tests describe a graph as an adjacency list, where adjList[i] lists the neighbors of the node with value i + 1. The tests turn your copy back into an adjacency list, so the expected output matches the input. If your copy reuses a node from the original graph, the tests report [[-1]].
Example 1
Input: adjList = [[2, 4], [1, 3], [2, 4], [1, 3]] Output: [[2, 4], [1, 3], [2, 4], [1, 3]] 1 --- 2 | | 4 --- 3
Node 1 is connected to nodes 2 and 4, node 2 to nodes 1 and 3, and so on.
Example 2
Input: adjList = [[]] Output: [[]]
The graph has a single node with no neighbors.
Constraints
- The graph has between
0and100nodes. An empty graph meansnodeis null. - Each node's value is unique, from
1ton. - There are no repeated edges and no edges from a node to itself.
- The graph is connected, so every node can be reached from the given node.
Approach
The copy needs exactly one new node for every original node, and its edges have to point at other new nodes, never at originals. Because the graph can have cycles, a traversal reaches some nodes more than once, so you need a way to find the copy you already made.
A hash map from each original node to its copy handles both jobs. A node that's in the map has already been copied and queued, so you don't visit it again. The map also gives you the copy to link to when you add an edge. Run a breadth-first search from the given node: copy each neighbor the first time you see it, and add the neighbor's copy to the current node's copy.
Steps
- If
nodeis null, return null. - Copy the starting node, store the pair in a map, and add the starting node to a queue.
- While the queue isn't empty, remove a node. For each of its neighbors that isn't in the map, copy the neighbor, store the pair and add the neighbor to the queue.
- Append the neighbor's copy to the neighbors of the current node's copy.
- When the queue is empty, return the copy of the starting node.
Complexity
- Time:
O(V + E), whereVis the number of nodes andEis the number of edges. Each node is copied and removed from the queue once, and each edge is followed once from each end. - Space:
O(V)for the map and the queue.
Common mistakes
- Adding an original neighbor to a copy's neighbor list instead of the neighbor's copy. The copy then links back into the original graph.
- Creating a new copy every time you reach a node. Because of cycles, this either loops forever or makes several copies of the same node.
- Adding a node to the map only when it leaves the queue. The same neighbor can then be queued and copied more than once.
Interview experiences
1 sharedRelated courses


