How do you solve Clone Graph on LeetCode?

Clone Graph (LeetCode #133) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a hash map to track cloned nodes avoids unnecessary duplication.

What is the brute force solution for Clone Graph?

The brute force approach for Clone Graph is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves creating a new node for each node in the graph and manually connecting them based on the original graph's structure. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Clone Graph?

Clone Graph uses the following concepts: Hash Table, Depth-First Search, Breadth-First Search, Graph Theory. The recommended patterns to study are: Hash Map, Graph Traversal.

What are the interview tips for Clone Graph?

Explain your thought process clearly while coding. Discuss edge cases, such as an empty graph or a graph with one node. Practice DFS and BFS traversal techniques as they are commonly used in graph problems.

What are common mistakes when solving Clone Graph?

Failing to check if a node has already been cloned, leading to infinite loops. Not handling the case where the input node is null.

#133

Clone Graph

Medium

Hash TableDepth-First SearchBreadth-First SearchGraph TheoryHash MapGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a depth-first search (DFS) approach with a hash map to keep track of already cloned nodes, ensuring that we only create each node once and connect them efficiently.

⚙️

Algorithm

3 steps

1Step 1: If the input node is null, return null.
2Step 2: Create a hash map to store cloned nodes.
3Step 3: Use DFS to traverse the graph, cloning nodes and their neighbors as you go, checking the hash map to avoid duplicates.

solution.py19 lines

1# Full working Python code
2class Node:
3    def __init__(self, val=0, neighbors=None):
4        self.val = val
5        self.neighbors = neighbors if neighbors is not None else []
6
7def cloneGraph(node):
8    if not node:
9        return None
10    clone_map = {}
11    def dfs(n):
12        if n in clone_map:
13            return clone_map[n]
14        clone = Node(n.val)
15        clone_map[n] = clone
16        for neighbor in n.neighbors:
17            clone.neighbors.append(dfs(neighbor))
18        return clone
19    return dfs(node)

ℹ

Complexity note: The optimal solution runs in O(n) time because we visit each node once, and the space complexity is O(n) due to the storage of cloned nodes in the hash map.

1Using a hash map to track cloned nodes avoids unnecessary duplication.
2Depth-first search is an effective way to traverse and clone graphs.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.