Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Clone Graph
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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.

Example 1:

Input:

    1--2
    |  |
    4--3

Expected Output:

    1--2
    |  |
    4--3

Explanation: The graph has four nodes with the following connections:

  • Node 1 is connected to nodes 2 and 4.
  • Node 2 is connected to nodes 1 and 3.
  • Node 3 is connected to nodes 2 and 4.
  • Node 4 is connected to nodes 1 and 3.

Example 2:

Input:

    1--2
   /    \
  5      3
         |
         4

Expected Output:

    1--2
   /    \
  5      3
         |
         4

Explanation: The graph consists of five nodes with these connections:

  • Node 1 is connected to nodes 2 and 5.
  • Node 2 is connected to nodes 1 and 3.
  • Node 3 is connected to nodes 2 and 4.
  • Node 4 is connected to node 3.
  • Node 5 is connected to node 1.

Example 3:

Input:

    1--2
   /    \
  4      3
   \    /
    5--6

Expected Output:

    1--2
   /    \
  4      3
   \    /
    5--6

Explanation: The graph has six nodes with the following connections:

  • Node 1 is connected to nodes 2 and 4.
  • Node 2 is connected to nodes 1 and 3.
  • Node 3 is connected to nodes 2 and 6.
  • Node 4 is connected to nodes 1 and 5.
  • Node 5 is connected to nodes 4 and 6.
  • Node 6 is connected to nodes 3 and 5.

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.

Solution

To deep clone a given graph, the primary approach is to traverse the graph using Depth-First Search (DFS) and simultaneously create clones of the visited nodes. A hashmap (or dictionary) is utilized to track and associate original nodes with their respective clones, ensuring no duplications.

  1. Initialization: Create an empty hashmap to match the original nodes to their clones.

  2. DFS Traversal and Cloning: Traverse the graph with DFS. When encountering a node not in the hashmap, create its clone and map them in the hashmap. Recursively apply DFS for each of the node's neighbors. After cloning a node and all its neighbors, associate the cloned node with the clones of its neighbors.

  3. Termination: Once DFS covers all nodes, return the cloned version of the starting node.

Algorithm Walkthrough (using Example 1):

For the input graph:

    1--2
    |  |
    4--3
  • Start with an empty hashmap visited.
  • Begin DFS with node 1.
    • Node 1 isn't in visited. Clone it to get 1' and map (1, 1') in the hashmap.
    • For each neighbor of node 1, apply DFS.
      • First with 2.
        • Node 2 isn't in visited. Clone to get 2' and map (2, 2').
        • Node 2's neighbors are 1 and 3. Node 1 is visited, so link 2' to 1'. Move to 3.
          • Node 3 isn't in visited. Clone to get 3' and map (3, 3').
          • Node 3 has neighbors 2 and 4. Node 2 is visited, so link 3' to 2'. Move to 4.
            • Node 4 isn't in visited. Clone to get 4' and map (4, 4').
            • Node 4 has neighbors 1 and 3, both visited. Link 4' to 1' and 3'.
  • With DFS complete, return the clone of the starting node, 1'.

Code

Python3
Python3
. . . .

Complexity Analysis

  • Time Complexity: O(N+M) where N is the number of nodes and M is the number of edges. Each node and edge is visited once.

  • Space Complexity: O(N) as we are creating a clone for each node. Additionally, the recursion stack might use O(H) where H is the depth of the graph (in the worst case this would be O(N).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible