MediumNo. 0133

Clone Graph — LeetCode 133 Python Solution

Topics
Depth-First Search, Breadth-First Search, Graph, Hash Table
Reading time
4 min

The problem

Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph.

Example

Example
class Node {
    public int val;
    public List<Node> neighbors;
}

Python solution

PythonSolution
"""
# 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

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.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.