Clone Graph — LeetCode 133 Python Solution
MediumDepth-First SearchBreadth-First SearchGraphHash Table
- Problem
- #133
- Pattern
- Breadth-First Search
- 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
Python
"""
# 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
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
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
On study lists
This problem is on Blind 75, NeetCode 150, Grind 75 and Top Interview 150.
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.