MediumNo. 0133
Clone Graph — LeetCode 133 Python Solution
- Pattern
- Breadth-First Search
- Topics
- Depth-First Search, Breadth-First Search, Graph, Hash Table
- On study lists
- Blind 75, NeetCode 150, Grind 75 and Top Interview 150
- Reading time
- 4 min
- Source
- leetcode.com
The problem
Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph.
Example
class Node {
public int val;
public List<Node> neighbors;
}Python solution
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
from typing import Optional
class Solution:
def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:
def dfs(node):
if node is None:
return None
if node in g:
return g[node]
cloned = Node(node.val)
g[node] = cloned
for nxt in node.neighbors:
cloned.neighbors.append(dfs(nxt))
return cloned
g = defaultdict()
return dfs(node)Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Breadth-First Search
Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 133. Clone Graph is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.
The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0924 | Minimize Malware Spread | Hard |
| 0928 | Minimize Malware Spread II | Hard |
| 2368 | Reachable Nodes With Restrictions | Medium |
| 0653 | Two Sum IV - Input is a BST | Easy |
| 0690 | Employee Importance | Medium |
| 0721 | Accounts Merge | Medium |
Frequently asked questions
- How hard is LeetCode 133. Clone Graph?
LeetCode 133. Clone Graph is rated Medium on LeetCode.
- What is the time complexity of LeetCode 133. Clone Graph?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 133. Clone Graph?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 133. Clone Graph cover?
LeetCode 133. Clone Graph is tagged Depth-First Search, Breadth-First Search, Graph and Hash Table on LeetCode.