Clone Graph
Medium · Graphs · Hash Table · Depth-First Search · Breadth-First Search · Graph
Problem
You are given one node of a connected, undirected graph. Return a deep copy of the whole graph: a new node for every node of the original, with the same val, joined by the same edges.
Each node has an integer val and a list neighbors of the nodes it is joined to. The node you are given has val = 1, and the values are 1 to n with no repeats. For an empty graph you get None and should return None.
The copy must not share any node with the original, and the original must not change. The tests read your copy with to_adj, which lists every node’s neighbours in order of val, so each new node must keep its neighbours in the same order as the node it copies.
The node type and two helpers are provided:
Some tests are a path of thousands of nodes, entered at one end, which is deeper than Python’s recursion limit.
Examples
Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]]
Four nodes in a cycle. The copy has four new nodes joined the same way: 1 to 2 and 4, 2 to 1 and 3, and so on.
Input: adjList = [[]] Output: [[]]
A single node with no neighbours. Its copy is a new node with val 1 and no neighbours.
Constraints
- 0 <= number of nodes <= 3000 (LeetCode stops at 100)
- Node.val is unique, from 1 to the number of nodes
- no repeated edges and no self-loops
- the graph is connected, and the given node has val 1
Approaches
- Recursive DFS with a map — time O(V + E), space O(V)
Related problems
Start free on Cariara · Coding problems · System design studio
