Clone Graph

MediumGraphDFSBFSHash Table
Category: Graphs
Companies that ask this question:
AmazonFacebookGoogleMicrosoftBloomberg

Approach

Clone Graph

Problem Statement

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.

class Node {
    public int val;
    public List<Node> neighbors;
}

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

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 (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
- 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
- 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.

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.

Approach

Key Insight

Use a hash map to track original → clone mapping!

This prevents:

  1. Creating duplicate clones
  2. Infinite loops in cyclic graphs
  3. Correctly handling shared neighbors

Solution 1: DFS (Depth-First Search)

Recursively clone nodes and their neighbors.

Algorithm:

  1. Create hash map: original → clone
  2. DFS function:
    • If node already cloned, return clone
    • Create new node (clone)
    • Store in hash map
    • Recursively clone all neighbors
    • Add cloned neighbors to clone's neighbor list
  3. Return clone of starting node

Solution 2: BFS (Breadth-First Search)

Iteratively clone using a queue.

Algorithm:

  1. Create hash map: original → clone
  2. Create queue, add starting node
  3. While queue not empty:
    • Get node from queue
    • If not cloned, create clone
    • For each neighbor:
      • If not cloned, create clone and add to queue
      • Add cloned neighbor to clone's neighbors
  4. Return clone of starting node

Solution 3: Iterative DFS with Stack

Use explicit stack instead of recursion.

Algorithm:

Same as DFS but use stack data structure instead of recursion call stack.

Complexity Analysis

DFS/BFS Solution:

  • Time Complexity: O(V + E) - visit each node and edge once
  • Space Complexity: O(V) - hash map stores all nodes

Where V = number of nodes, E = number of edges

Pattern Recognition

This problem demonstrates:

  • Graph traversal (DFS/BFS)
  • Deep copy with hash map tracking
  • Cycle handling in graphs
  • Reference vs value semantics
  • Foundation for graph cloning problems

Solution

java
1import java.util.*;
2
3// Definition for a Node.
4class Node {
5    public int val;
6    public List<Node> neighbors;
7
8    public Node() {
9        val = 0;
10        neighbors = new ArrayList<Node>();
11    }
12
13    public Node(int _val) {
14        val = _val;
15        neighbors = new ArrayList<Node>();
16    }
17
18    public Node(int _val, ArrayList<Node> _neighbors) {
19        val = _val;
20        neighbors = _neighbors;
21    }
22}
23
24class Solution {
25    // Solution 1: DFS (Depth-First Search)
26    private Map<Node, Node> clones = new HashMap<>();
27
28    public Node cloneGraph(Node node) {
29        if (node == null) return null;
30
31        // If already cloned, return the clone
32        if (clones.containsKey(node)) {
33            return clones.get(node);
34        }
35
36        // Create clone
37        Node clone = new Node(node.val);
38        clones.put(node, clone);
39
40        // Clone all neighbors recursively
41        for (Node neighbor : node.neighbors) {
42            clone.neighbors.add(cloneGraph(neighbor));
43        }
44
45        return clone;
46    }
47
48    // Solution 2: BFS (Breadth-First Search)
49    public Node cloneGraphBFS(Node node) {
50        if (node == null) return null;
51
52        // Hash map: original -> clone
53        Map<Node, Node> clones = new HashMap<>();
54
55        // Create clone of starting node
56        clones.put(node, new Node(node.val));
57
58        // BFS queue
59        Queue<Node> queue = new LinkedList<>();
60        queue.offer(node);
61
62        while (!queue.isEmpty()) {
63            Node curr = queue.poll();
64
65            // Process all neighbors
66            for (Node neighbor : curr.neighbors) {
67                if (!clones.containsKey(neighbor)) {
68                    // Create clone for unvisited neighbor
69                    clones.put(neighbor, new Node(neighbor.val));
70                    queue.offer(neighbor);
71                }
72
73                // Add cloned neighbor to current clone's neighbors
74                clones.get(curr).neighbors.add(clones.get(neighbor));
75            }
76        }
77
78        return clones.get(node);
79    }
80
81    // Solution 3: Iterative DFS with Stack
82    public Node cloneGraphIterative(Node node) {
83        if (node == null) return null;
84
85        // Hash map: original -> clone
86        Map<Node, Node> clones = new HashMap<>();
87        clones.put(node, new Node(node.val));
88
89        // DFS stack
90        Stack<Node> stack = new Stack<>();
91        stack.push(node);
92
93        while (!stack.isEmpty()) {
94            Node curr = stack.pop();
95
96            // Process all neighbors
97            for (Node neighbor : curr.neighbors) {
98                if (!clones.containsKey(neighbor)) {
99                    // Create clone for unvisited neighbor
100                    clones.put(neighbor, new Node(neighbor.val));
101                    stack.push(neighbor);
102                }
103
104                // Add cloned neighbor to current clone's neighbors
105                clones.get(curr).neighbors.add(clones.get(neighbor));
106            }
107        }
108
109        return clones.get(node);
110    }
111}
112
Loading visualizer...