Course4all

Clone Graph

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Graphs.

Clone Graph

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.

Visual Representation

1 -- 2 | | 4 -- 3 Clone: 1' -- 2' | | 4' -- 3'
Medium

Examples

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Node 1 is connected to 2 and 4. Node 2 is connected to 1 and 3, etc.
Approach 1

Level II: Intermediate (BFS + HashMap)

Intuition

BFS uses a queue to visit nodes level-by-level. By using a HashMap to store original -> clone, we can manage complexity and cycles. Every time we encounter a neighbor, if it's not in the map, we clone it and add to the queue.

Thought Process

  1. Use a HashMap to store originalNode -> clonedNode.
  2. Push the start node to a queue and create its clone.
  3. While the queue is not empty:
    • Pop curr. For each neighbor nbr:
      • If nbr is NOT in the map (unvisited):
        • Create its clone and add it to the map.
        • Push nbr to the queue.
      • Add the cloneMap.get(nbr) to the cloneMap.get(curr)'s neighbors list.
  4. Return the clone of the input node.

Pattern: BFS with Mapping

⏱ O(V + E) - Standard BFS traversal.💾 O(V) - For the queue and the mapping.

Detailed Dry Run

1 -- 2
MapQueueAction
{1:1'}[1]Init
{1:1', 2:2'}[2]Pop 1, clone 2, add 2' to 1' neighbors
{1:1', 2:2'}[]Pop 2, 1 is in map, add 1' to 2' neighbors
java
import java.util.*;

public class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> map = new HashMap<>();
        map.put(node, new Node(node.val));
        Queue<Node> q = new LinkedList<>();
        q.add(node);

        while (!q.isEmpty()) {
            Node curr = q.poll();
            for (Node nbr : curr.neighbors) {
                if (!map.containsKey(nbr)) {
                    map.put(nbr, new Node(nbr.val));
                    q.add(nbr);
                }
                map.get(curr).neighbors.add(map.get(nbr));
            }
        }
        return map.get(node);
    }
}
Approach 2

Level III: Optimal (DFS + HashMap)

Intuition

DFS is often more concise for graph cloning as it mimics the structure of the graph through the call stack. The HashMap acts as our "visited" set while also storing the deep copies.

Thought Process

  1. Use a HashMap to store originalNode -> clonedNode.
  2. In DFS function:
    • If the node is NULL, return NULL.
    • If the node is already in the map, return the existing clone.
    • Otherwise, create a new clone and add it to the map.
    • For each neighbor of the original node, recursively call DFS and add the result to the clone's neighbor list.
  3. Return the DFS call for the input node.

Pattern: DFS with Mapping

⏱ O(V + E) - Each node and edge is visited once.💾 O(V) - For the recursion stack and the mapping.

Detailed Dry Run

1 -> [2, 4]
MapCallAction
{}DFS(1)Create 1', Map {1:1'}, Call DFS(2)
{1:1'}DFS(2)Create 2', Map {1:1', 2:2'}, Call DFS(3)
.........
{1:1', 2:2', 3:3', 4:4'}DFS(4)Return 4' to 1' neighbors list
java
import java.util.*;

public class Solution {
    private Map<Node, Node> visited = new HashMap<>();
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (visited.containsKey(node)) return visited.get(node);

        Node clone = new Node(node.val);
        visited.put(node, clone);

        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }
        return clone;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionNumber of Islands
Next Question →Pacific Atlantic Water Flow