Medium

Clone Graph

048

Given an undirected graph adjacency list, return a deep-cloned adjacency list with the same structure.

EXAMPLES

Example 1

Input
{
  "graph": [
    [
      2,
      4
    ],
    [
      1,
      3
    ],
    [
      2,
      4
    ],
    [
      1,
      3
    ]
  ]
}

Output
[
  [
    2,
    4
  ],
  [
    1,
    3
  ],
  [
    2,
    4
  ],
  [
    1,
    3
  ]
]

FUNCTION SHAPE

graph: intMatrix→intMatrix

SOLUTION NOTE

This is similar to the clone linked list question. Basically we need a map from old nodes to new nodes. We use BFS to traverse the graph, and if this is neighbour is an old node we haven't created a new node for yet, we create it and update the map. We then update the current new nodes neighbour with the new node of that neighbour.

Try to compare with the DFS solution. Why must we initialize the dict with the source node in bfs, but not in dfs? Because in bfs, we need to add the new neighbouring node. If we add the current node to the map we won't have access to the neighbour node in the map, so we have to initialize the map with the source and add neighbouring nodes to the map. Another nice thing about the dfs solution, is that we are using the map as the visited set as well! Ie. if the node is in the map, it was definitely visited before. Think about what dfs(node) means, it returns the new node of the given 'node' in the new graph, so we can use it recursively clone.neighbors.append(dfs(neighbor))

Reveal reference solution +

pythonREFERENCE

# BFS Solution
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
    if not node: return None

    node_map = {node: Node(node.val)}
    q = deque([node])
    visited = set()

    while q:
        curr = q.popleft()

        if curr in visited: continue
        visited.add(curr)
        for nbr in curr.neighbors:
            if nbr not in node_map:
                node_map[nbr] = Node(nbr.val)

            node_map[curr].neighbors.append(node_map[nbr])
            q.append(nbr)

    return node_map[node]

# DFS Solution
def cloneGraph(self, node: 'Node') -> 'Node':
    old_to_new = {}

    def dfs(n):
        if n in old_to_new:
            return old_to_new[n]

        clone = Node(n.val)
        old_to_new[n] = clone
        for neighbor in n.neighbors:
            clone.neighbors.append(dfs(neighbor))
        return clone

    return dfs(node) if node else None

TimeO(n+m)

SpaceO(n)

Open on LeetCode ↗