Design Gurus Logo
Blind 75

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.

Why this is a Clone problem

What the question saysThe signal it matches
"return a deep copy (clone) of the graph"the word clone, copy, or duplicate appears, together with a linked structure
"Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors."nodes hold pointers to other nodes beyond a simple parent to child link
"Node 1 is connected to nodes 2 and 4."the structure may contain cycles, or a pointer to a node not yet visited

This is the many neighbours, with cycles variant: every neighbour, including ones already being copied.

The closest alternative. There is none that removes the map. Every route to a correct answer must remember which originals are already copied. That memory can sit in a map, in a visited set, or in a field on the node.

Example 1 is a four node cycle, which is the whole difficulty. Copy a node, then copy the nodes it connects to, and you return to where you started. The order that fixes it is fixed. Create the copy and put it in the map first, then walk the connections. Copying first and inserting afterwards lets the recursion re-enter the same node and never stop.

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

Let's trace the first example, the four node cycle. Move through the steps one at a time:

mediaLink

Step 1. The four nodes form a cycle: following the connections from 1 leads back to 1. A plain walk would go round it forever, so something has to remember which originals already have a copy, and that is the map. The order matters more than it looks. Make the copy and put it in the map first, then walk the connections. Doing it the other way round lets the walk re-enter a node it is already inside, and it never stops.

1 of 6

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).

No code editor for this lesson
This lesson focuses on concepts and theory