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

0% completed

Vote For New Content
Clone Graph (medium)
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.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

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