mafeshsho8lmafeshsho8l
Get Started
All coding questions

Clone Graph

medium
NeetCode 150graphsdfsbfshashing

Problem

Given a reference to a node in a connected undirected graph, return a deep copy of the whole graph. Each cloned node must hold the same value and a list of its cloned neighbours.

Examples

Input: a 4-node cycle graph
Output: an independent identical 4-node cycle
The copy shares no node objects with the original.

Constraints

  • • 0 <= number of nodes <= 100
  • • The graph is connected and undirected
Hints(tap to reveal)
  • 1. Map original nodes to their clones to avoid infinite loops.
  • 2. Create a clone on first visit, then wire neighbours.
Optimal approach(spoiler)
  1. Keep a hash map from original node to its clone.
  2. Traverse with DFS or BFS starting from the given node.
  3. Create a clone the first time a node is seen and record it.
  4. For each neighbour, recurse or enqueue, then attach its clone.
  5. O(V + E) time, O(V) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor