Clone Graph DSA Solution

Learning Outcome

After this lesson, you should be able to use a map from original nodes to clone nodes so cycles do not create duplicate copies.

Problem Statement

Given a reference to a node in a connected undirected graph, return a deep copy of the graph.

Input	Output	Why
`adjList = [[2,4],[1,3],[2,4],[1,3]]`	`A separate graph with the same values and neighbor links`	Each original node has exactly one clone, and cloned neighbors point to cloned nodes.

Brute Force Approach

Create a new node every time a neighbor is seen. In cyclic graphs this duplicates nodes and can recurse forever.

Optimized Approach

DFS from the start node. Store each original node in a map as soon as its clone is created, then recursively clone neighbors.

Exact Pseudocode

clone(node):
  if node is null:
    return null
  if node exists in map:
    return map[node]
  copy = new Node(node.val)
  map[node] = copy
  for neighbor in node.neighbors:
    copy.neighbors.add(clone(neighbor))
  return copy

Reference Code

class Solution:
    def cloneGraph(self, node):
        clones = {}

        def dfs(cur):
            if not cur:
                return None
            if cur in clones:
                return clones[cur]

            copy = Node(cur.val)
            clones[cur] = copy
            for nei in cur.neighbors:
                copy.neighbors.append(dfs(nei))
            return copy

        return dfs(node)

Sample Dry Run

Step	State	Result
Visit node 1	Create clone 1 and store map[1]	Cycle protection starts
Clone neighbor 2	Create clone 2	Add it to clone 1 neighbors
Neighbor points back	DFS sees node 1 already in map	Reuse clone 1
Finish	Every original maps to one clone	Return clone of start

Complexity

Measure	Value	Reason
Time	O(v + e)	Every node and neighbor edge is visited once.
Space	O(v)	The clone map and recursion stack store graph nodes.

Edge Cases

Null input should return null.
Cycles must reuse existing clones.
Do not share original neighbor references in the clone.

Interview Checklist

Put the clone in the map before cloning neighbors.
Use node references as map keys.
Return the cloned start node, not the original node.

FAQs

Why store clone before neighbors?

A cycle can point back to the current node. The map must already know the clone to stop infinite recursion.

Is this a deep copy?

Yes, every node is new, and every neighbor link points to cloned nodes.

What is the core pattern?

DFS with an original-to-copy hash map.

Clone Graph: Hash Map DFS Pattern