133. Clone Graph
Clone Graph (LeetCode 133) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Deep Copy / Cloning subpattern.
How to solve Clone Graph
Clone Graph is a Graph Deep Copy and Cloning problem, part of Graph Traversal Patterns (DFS & BFS). Learn to deep copy and clone graph structures using DFS/BFS with visited mapping.
Work towards the solution in these steps:
- Consider how graph traversal techniques like DFS or BFS can help you visit all nodes starting from the given node.
- Think about how to avoid revisiting nodes and handle cycles during traversal to prevent infinite loops.
- To clone the graph, you'll need a way to create new nodes while preserving the original graph structure; consider using a mapping from original nodes to their clones.
The reference solution runs in O(N + E) time and O(N + E) space.
The Clone Graph solution and editorial walks through the full approach with reference code.
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.
class Node { public int val; public List<Node> neighbors; }
Test case format:
For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
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 empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Example 3:
Input: adjList = [] Output: [] Explanation: This an empty graph, it does not have any nodes.
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.
Topics and companies
Topics: Hash Table, Depth-First Search, Breadth-First Search, Graph.
Reported in interviews at Adobe, Amazon, Apple, Bloomberg, Facebook, Google, Microsoft, Qualtrics, Twitter, Uber.
How to practise Clone Graph on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N + E) time and O(N + E) space.
Open Clone Graph in the code editor, or read the Clone Graph editorial for a worked solution with its approach and complexity analysis.
Where Clone Graph sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Deep Copy / Cloning subpattern
- The full DSA patterns sheet
Problems related to Clone Graph
Other problems that use the same Deep Copy / Cloning and Graph Traversal Patterns (DFS & BFS) techniques:
- Clone N-ary Tree — Medium, same subpattern
- Copy List with Random Pointer — Medium, same subpattern
- Find the City With the Smallest Number of Neighbors at a Threshold Distance — Medium, same subpattern
- Accounts Merge — Medium, same pattern
- Alien Dictionary — Hard, same pattern
- All Paths from Source Lead to Destination — Medium, same pattern
Clone Graph FAQ
What is the LeetCode number of Clone Graph?
Clone Graph is LeetCode problem 133, rated Medium.
What pattern is used to solve Clone Graph?
Clone Graph is a Graph Deep Copy and Cloning problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Deep Copy / Cloning subpattern.
What is the time complexity of Clone Graph?
The reference solution runs in O(N + E) time and O(N + E) space.
Which companies ask Clone Graph?
Clone Graph has been reported in interviews at Adobe, Amazon, Apple, Bloomberg, Facebook, Google, Microsoft, Qualtrics, Twitter, Uber.