LC-0133 Medium LeetCode

133. Clone Graph

Hash Table Depth-First Search Breadth-First Search Graph

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 62% Topics: Hash Table, Depth-First Search, Breadth-First Search, Graph

Reading material

Arrays & Hashing 12 min Trees & Traversals 18 min Graphs 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class UndirectedGraphNode(object):
    def __init__(self, x):
        self.label = x
        self.neighbors = []

class Solution(object):
    # @param node, a undirected graph node
    # @return a undirected graph node
    def cloneGraph(self, node):
        if node is None:
            return None
        cloned_node = UndirectedGraphNode(node.label)
        cloned, queue = {node:cloned_node}, [node]

        while queue:
            current = queue.pop()
            for neighbor in current.neighbors:
                if neighbor not in cloned:
                    queue.append(neighbor)
                    cloned_neighbor = UndirectedGraphNode(neighbor.label)
                    cloned[neighbor] = cloned_neighbor
                cloned[current].neighbors.append(cloned[neighbor])
        return cloned[node]

Solution from kamyu104/LeetCode-Solutions · MIT