LeetCode 133. Clone Graph

December 18, 2024

This problem stumped me for a while because I needed to use a dictionary to make sure I didn't have duplicate copies, then I also forgot to return the copy at the end of the DFS algorithm.

Solution

1"""
2# Definition for a Node.
3class Node:
4    def __init__(self, val = 0, neighbors = None):
5        self.val = val
6        self.neighbors = neighbors if neighbors is not None else []
7"""
8from typing import Optional
9class Solution:
10    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
11        if not node:
12            return None
13
14        copies = {}
15
16        def dfs(node):
17            if node in copies:
18                return copies[node]
19            
20            copy = Node(node.val)
21            copies[node] = copy
22            for n in node.neighbors:
23                copy.neighbors.append(dfs(n))
24            
25            return copy
26        
27        dfs(node)
28
29        return copies[node]

The time complexity is O(V + E) since we visit every node and edge once, and then the space complexity is O(V) because our copies dictionary is always the number of verticies in the graph. The recursive call stack is also at worst case O(V) space complexity.

LeetCode 173. Binary Search Tree Iterator

LeetCode 77. Combinations