TIC
The Interns Company

Clone Graph

MediumAcceptance: 61.6%
Hash TableBreadth-First SearchDepth-First SearchGraph

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.

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

Input Format:

  • A reference to a node in a connected undirected graph

Output Format:

  • A deep copy (clone) of the graph

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 node with val = 1 and no neighbors.

Example 3:

Input:

adjList = []

Output:

[]

Explanation:

This is an empty graph with no nodes.

Solutions

DFS with Hash Map

Time: O(V + E) where V is the number of vertices and E is the number of edges
Space: O(V)

Use depth-first search with a hash map to keep track of cloned nodes.

BFS with Hash Map

Time: O(V + E) where V is the number of vertices and E is the number of edges
Space: O(V)

Use breadth-first search with a hash map to keep track of cloned nodes.

Algorithm Walkthrough

Example input:

Step-by-step execution:

  1. Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
  2. This represents a graph with 4 nodes:
  3. - Node 1 is connected to nodes 2 and 4
  4. - Node 2 is connected to nodes 1 and 3
  5. - Node 3 is connected to nodes 2 and 4
  6. - Node 4 is connected to nodes 1 and 3
  7. Start DFS with node 1 as the entry point
  8. Create a visited map to store cloned nodes
  9. Create a cloned node 1 and add to visited map
  10. Process neighbors of node 1: [2, 4]
  11. For neighbor 2:
  12. Create a cloned node 2 and add to visited map
  13. Process neighbors of node 2: [1, 3]
  14. For neighbor 1: Already visited, get from map
  15. For neighbor 3:
  16. Create a cloned node 3 and add to visited map
  17. Process neighbors of node 3: [2, 4]
  18. For neighbor 2: Already visited, get from map
  19. For neighbor 4:
  20. Create a cloned node 4 and add to visited map
  21. Process neighbors of node 4: [1, 3]
  22. For neighbor 1: Already visited, get from map
  23. For neighbor 3: Already visited, get from map
  24. Return the cloned node 1, which is now the head of a deep copy of the graph

Hints

Hint 1
Use a hash map to store the mapping from original nodes to cloned nodes.
Hint 2
Use DFS or BFS to traverse the graph.
Hint 3
When visiting each node, create a clone if it doesn't exist and recursively clone its neighbors.

Video Tutorial

Clone Graph - DFS & BFS Approaches

YouTube•Learn the Clone Graph solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the cloning process as the graph is traversed, showing the original graph and the cloned graph side by side.

Key visualization elements:

  • current node being processed
  • edges being created
  • visited nodes

Asked By

AmazonFacebookGoogleMicrosoftLinkedInUberApple

Implementation Notes

This problem tests your understanding of graph traversal (DFS or BFS) and creating deep copies of complex data structures. Both approaches have the same time and space complexity, but DFS is often more intuitive for this problem.