133. Clone Graph

MediumDepth-First SearchBreadth-First SearchGraphHash Table
Leetcode Link

Problem Description

The problem is about creating a deep copy of a connected undirected graph. A deep copy means a new graph where each node and edge is a replica of the original graph but is an entirely new instance, with no shared references with the original graph.

In a graph, nodes are interconnected through edges. To represent this in code, each node has an integer value and a list of its neighboring nodes. The goal is to copy all the nodes and their connections in such a way that if you manipulate the copied graph, the original graph remains unaffected.

The representation of the graph is done using an adjacency list, which is an array of lists where each list represents a node and contains all of its neighbors. For the purposes of this problem, every node's value is assumed to be unique and equal to its 1-based index in the adjacency list, simplifying the graph's representation and the copying process.

The challenge here is to ensure that while copying the nodes, their neighbors are also copied correctly, and any neighbor connections in the new graph mirror those in the original graph, preserving the structure.

Intuition

To solve the problem, the idea is to traverse the graph, starting from the given node, and create new nodes as we go. Since the original graph could have cycles or shared neighbors, it is crucial to keep track of the nodes that have already been copied to avoid infinite loops and ensure that neighbors are not duplicated in the new graph.

The algorithm involves a depth-first search (DFS) traversal with the following steps:

  1. Initialize a visited dictionary that will map original nodes to their corresponding cloned nodes. This will help check if a node has been visited, and also provide a reference to its cloned counterpart.

  2. Define a recursive function clone(node) that takes a node from the original graph.

    • If the node is None, return None (this handles empty graph cases).
    • If the node has already been visited, return its cloned counterpart from the visited dictionary.
    • If the node is new, create a clone with the same value.
    • Store this cloned node in the visited dictionary with the original node as the key.
    • Iteratively clone all the neighbor nodes using the same clone function and append them to the neighbors list of the cloned node.

  3. Start the cloning process by calling clone(node) on the given node and return its result, which is a reference to the cloned graph's starting node.

By following these steps, we ensure that each node is visited once, and a deep copy of the graph is created, with all the original connections between the nodes preserved in the new graph.

Learn more about Depth-First Search, Breadth-First Search and Graph patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The solution leverages the depth-first search (DFS) algorithm to iterate through the graph, and a hash map (defaultdict in Python) to keep track of visited nodes and their clones. This ensures each node is copied exactly once, and we do not run into an infinite loop due to cycles in the graph.

Here's a step-by-step breakdown of the solution approach:

  1. Initialization:

    • A dictionary visited is created to map original nodes to their cloned counterparts. This is essential to:
      • Track which nodes have already been copied.
      • Retrieve the cloned version of a node to set up the neighbors references correctly in the cloned graph.

  2. Clone Function:

    • The clone function is a recursive helper function that performs the DFS.
    • The function signature clone(node) takes a node from the original graph as its argument.

  3. Base cases:

    • If the input node is None, meaning either the graph is empty or we've hit the end of a path, the function returns None.
    • If the input node is found in the visited dictionary, it means we've already created a clone of this node. We immediately return the cloned node to avoid duplicating nodes or falling into a cycle.

  4. Cloning Process:

    • If the node is being visited for the first time, we create a new Node instance with the same value (c = Node(node.val)).
    • The new node c is then stored in visited[node]. This step marks the node as copied and provides a reference for its clone.

  5. Neighbors Copy:

    • We then iterate over the neighbors of the current node. For each neighbor, we recursively call the clone function (clone(e)) and append the result to the c.neighbors.
    • This recursive approach ensures that we explore each neighbor (and subsequently, each neighbor's neighbor, and so on), cloning nodes and stitching together the cloned graph as we traverse the original graph.

  6. Returning the Clone:

    • Once all neighbors for the node have been processed, the function returns c, the clone of the current node, along with all its neighbors properly linked.

  7. Invocation:

    • The DFS cloning begins with return clone(node), where node is the reference to the node that was provided as input to the cloneGraph function.
    • Upon completion, this invocation returns a reference to the newly created deep copy of the graph, which can now be used independently of the original graph.

This solution scales well because the DFS and usage of a hash map ensure that each node is visited and copied exactly once. The complexity of the algorithm is O(N + M), where N is the number of nodes and M is the number of edges in the graph, since every node and edge is visited once in the traversal and copying process.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search can be used to find whether two components in a graph are connected.

Example Walkthrough

Let's say we have a small undirected graph represented by the adjacency list [[2,4],[1,3],[2,4],[1,3]], which corresponds to the following graph:

1Node 1 -- Node 2
2 |         |
3Node 4 -- Node 3

  1. Initialization:

    • We initialize an empty dictionary called visited to keep track of the cloned nodes.

  2. Start Cloning:

    • We begin by calling clone(node) on the node with value 1 (Node 1).

  3. Node 1:

    • Since Node 1 isn't in visited, we create a cloned node C1 and add it to visited with visited[1] = C1.
    • We proceed to clone Node 1's neighbors (Node 2 and Node 4).

  4. Node 2:

    • We call clone(node) on Node 1's first neighbor, Node 2.
    • Node 2 isn't in visited, so we create a clone C2 and add it to visited.
    • We then clone Node 2's neighbors (Node 1 and Node 3). Since Node 1 is already visited, we link C1 (Node 1's clone) as a neighbor to C2.

  5. Node 3:

    • When cloning Node 2's neighbors, we call clone(node) on Node 3.
    • Node 3 isn't in visited, so we create a clone C3 and add it to visited.
    • We clone Node 3's neighbors (Node 2 and Node 4). Node 2's clone, C2, is already in visited, so we link C2 as a neighbor to C3.

  6. Node 4:

    • Now, from Node 1, we clone the second neighbor, Node 4, by calling clone(node) on it.
    • We create C4 since Node 4 isn't in visited and add it to visited.
    • We clone Node 4's neighbors (Node 1 and Node 3). Clones for both these nodes (C1 and C3) are found in visited, so we link both as neighbors to C4.

  7. Completing the Graph:

    • With all nodes visited, the DFS cloning is complete. Each node in the graph is cloned exactly once, and their neighbors are interconnected following their original structure.

  8. Return:

    • We return C1, which now has C2 and C4 as its neighbors, representing the start of the cloned graph.

The cloned graph is now a deep copy of the original and can be manipulated without affecting the original graph. The connections are:

1C1 -- C2
2 |     |
3C4 -- C3

Each Ci denotes the cloned node corresponding to the original node of the same index. The deep copy process ensures that even if the initial graph had a more complex structure with cycles, the algorithm would have correctly cloned it without entering an infinite loop, since each node is visited only once.

Solution Implementation

1from collections import defaultdict
2
3class Node:
4    """
5    # Definition for a Node in the graph.
6    """
7    def __init__(self, val=0, neighbors=None):
8        self.val = val
9        self.neighbors = neighbors if neighbors is not None else []
10
11
12class Solution:
13    def cloneGraph(self, node: 'Node') -> 'Node':
14        # Dictionary to keep track of visited nodes and their clones.
15        visited = defaultdict(Node)
16
17        def clone(node: 'Node') -> 'Node':
18            """
19            clone is a helper function which performs a depth-first traversal
20            of the graph to create a deep copy of it.
21
22            :param node: The graph node to be cloned
23            :return: The cloned copy of the input node
24            """
25            # Return None for a non-existent node
26            if node is None:
27                return None
28          
29            # If the node has already been visited, return the cloned node
30            if node in visited:
31                return visited[node]
32          
33            # Create a new Node clone with the value of the original node
34            clone_node = Node(node.val)
35          
36            # Map the original node to the cloned one in visited dictionary
37            visited[node] = clone_node
38          
39            # For every adjacent node, create a clone copy to the neighbors of the cloned node
40            for neighbor in node.neighbors:
41                clone_node.neighbors.append(clone(neighbor))
42
43            return clone_node
44
45        # Start the graph cloning process from the input node
46        return clone(node)
47
1import java.util.HashMap;
2import java.util.List;
3import java.util.Map;
4
5// Definition for a graph node.
6class Node {
7    public int val;
8    public List<Node> neighbors;
9  
10    public Node() {
11        val = 0;
12        neighbors = new ArrayList<>();
13    }
14  
15    public Node(int _val) {
16        val = _val;
17        neighbors = new ArrayList<>();
18    }
19  
20    public Node(int _val, ArrayList<Node> _neighbors) {
21        val = _val;
22        neighbors = _neighbors;
23    }
24}
25
26class Solution {
27  
28    // A HashMap to keep track of all the nodes which have already been copied.
29    private Map<Node, Node> visited = new HashMap<>();
30
31    // This function returns the clone of the graph.
32    public Node cloneGraph(Node node) {
33        // If the input node is null, then return null.
34        if (node == null) {
35            return null;
36        }
37      
38        // If the node has already been visited i.e., already cloned,
39        // return the cloned node from the map.
40        if (visited.containsKey(node)) {
41            return visited.get(node);
42        }
43      
44        // Create a new node with the value of the input node (clone it).
45        Node cloneNode = new Node(node.val);
46        // Mark this node as visited by putting into the visited map.
47        visited.put(node, cloneNode);
48      
49        // Iterate over all the neighbors of the input node.
50        for (Node neighbor : node.neighbors) {
51            // Perform a depth-first search (DFS) for each neighbor,
52            // and add the clone of the neighbor to the neighbors list
53            // of the clone node.
54            cloneNode.neighbors.add(cloneGraph(neighbor));
55        }
56      
57        // Return the cloned graph node.
58        return cloneNode;
59    }
60}
61
1#include <unordered_map>
2#include <vector>
3
4// Forward declaration of the Node class to use it in the Solution.
5class Node {
6public:
7    int val;
8    std::vector<Node*> neighbors;
9    Node() : val(0) {}
10    Node(int _val) : val(_val) {}
11    Node(int _val, std::vector<Node*> _neighbors) : val(_val), neighbors(_neighbors) {}
12};
13
14class Solution {
15public:
16    // A dictionary to keep track of all visited nodes and their clones.
17    std::unordered_map<Node*, Node*> visited;
18
19    // Function to clone a graph.
20    Node* cloneGraph(Node* node) {
21        // If the input node is null, return null indicating no node to clone.
22        if (!node) return nullptr;
23
24        // If the node has been already visited, return the clone from visited.
25        if (visited.find(node) != visited.end()) return visited[node];
26
27        // Create a new node with the same value as the input node.
28        Node* cloneNode = new Node(node->val);
29        // Record the visited node by mapping the original node to the clone.
30        visited[node] = cloneNode;
31
32        // Iterate over all neighbors of the input node.
33        for (auto& neighbor : node->neighbors) {
34            // Recursively call cloneGraph for each neighbor and add it to the cloned node's neighbors.
35            cloneNode->neighbors.push_back(cloneGraph(neighbor));
36        }
37
38        // Return the cloned node.
39        return cloneNode;
40    }
41};
42
1// Function to clone a graph. Returns a cloned copy of the given graph node or null if the input node is null.
2function cloneGraph(originalNode: Node | null): Node | null {
3    // If the original node is null, return null as there is nothing to clone.
4    if (originalNode === null) return null;
5
6    // Map to hold visited nodes to avoid duplication and for constant-time look-up.
7    const visitedMap = new Map<Node, Node>();
8
9    // Clone the original node and store the mapping.
10    visitedMap.set(originalNode, new Node(originalNode.val));
11
12    // Queue for BFS traversal starting at the original node.
13    const queue: Node[] = [originalNode];
14
15    // Traverse the graph in a breadth-first manner
16    while (queue.length > 0) {
17        // Remove the first node from the queue to process its neighbors.
18        const currentNode = queue.shift();
19
20        // Process all the neighbors of the current node.
21        for (let neighbor of currentNode.neighbors) {
22            // If this neighbor hasn't been visited/processed yet.
23            if (!visitedMap.has(neighbor)) {
24                // Clone the neighbor and put it in the map.
25                queue.push(neighbor);
26                visitedMap.set(neighbor, new Node(neighbor.val));
27            }
28            // Add the cloned neighbor to the neighbors list of the cloned current node.
29            const clonedCurrentNode = visitedMap.get(currentNode);
30            clonedCurrentNode.neighbors.push(visitedMap.get(neighbor));
31        }
32    }
33    // Return the cloned node that corresponds to the original input node.
34    return visitedMap.get(originalNode);
35}
36
Not Sure What to Study? Take the 2-min Quiz๏ผš

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Time and Space Complexity

Time Complexity

The time complexity of the cloneGraph function is O(N + M), where N is the number of nodes in the graph and M is the number of edges. This is because each node is visited exactly once during the clone operation. When visiting each node, all of its neighbors are iterated through to copy their references, contributing to the M term in the complexity.

Space Complexity

The space complexity of the cloneGraph function is also O(N), where N is the number of nodes in the graph. This space is used to store cloned nodes in the visited dictionary to keep track of already cloned nodes, ensuring nodes are not cloned multiple times. The space complexity also includes the recursion stack, which in case of a deep graph could be O(N) in the worst case (when the graph is a linked list). However, in the average case of a typical graph, the recursion stack will not grow linearly with the number of nodes and will be smaller.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ