Skip to main content

133. Clone Graph

medium

Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Tests whether you can traverse a graph and build a parallel structure in one pass using a hash map to break the visited-cycle problem.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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.

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.

Examples

Example 1

Input
adjList = [[2,4],[1,3],[2,4],[1,3]]
Output
[[2,4],[1,3],[2,4],[1,3]]

Explanation: There are 4 nodes in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node's neighbors are 1st node and 3rd node. And so on.

Example 2

Input
adjList = [[]]
Output
[[]]

Explanation: Single node with no neighbors.

Example 3

Input
adjList = []
Output
[]

Explanation: Empty graph — no nodes.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If you just DFS naively, cycles in the graph will trap you in infinite recursion. What state do you need to track?

Hint 2

Maintain a hash map from original node -> cloned node. Before recursing into a neighbor, check the map.

Hint 3

On first visit to a node: create its clone, store original->clone in the map, then recurse into each original neighbor to clone-or-fetch and append to the new node's neighbors list.

Solution approach

Reveal approach

DFS (or BFS) with a hash map from original-node to cloned-node. Base case: input is null -> return null. Define dfs(node): if node is in the map, return the cached clone (this is what breaks cycles); otherwise create a new node with the same val, store map[node] = clone immediately (so neighbors recursing back to this node see it as visited), then iterate node.neighbors and push dfs(neighbor) into clone.neighbors. Return clone. The early map-set is the trick — doing it after recursion would cause infinite cycles. O(V + E) time, O(V) space for the map plus recursion stack.

Complexity

Time
O(V + E)
Space
O(V)

Related patterns

  • dfs
  • bfs
  • hash-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft
  • Bloomberg

More Graphs practice problems

See all Graphs problems →