Problem Statement in English

You’re given a graph. Your task is to return a deep copy of it.

This means that you have to create a copy of the graph, without using any references from the original one. Every node must be a freshly allocated.

Approach

Every node is made up of 2 parts: its value, and its neighbors. But here’s the problem with that - each neighbor will also list this node as a neighbor. Which means that in order to complete this node, we need to complete the neighbor, and in order to complete the neighbor we need to complete this node. There’s a cyclic dependency. Fortunately for us, we can leverage references.

Long story short, we store each node partially, and update them as we go. In order to deal with the cyclic dependency issue, we use a recursive approach, here’s an example:

    graph LR
    A((L)) --- B((M))
    B --- C((R))

Let’s call the nodes left ($l$), middle ($m$) and right ($r$).

Say we begin at $l$. We notice that it has a neighbor $m$. So we start processing $m$. Then we see that $m$ has a neighbor $r$. So we process $r$, and then get back to $m$ with the processed $r$. Next we resume processing $l$, and Bob’s your uncle.

Solution in Python


class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors: List["Node"] = neighbors if neighbors is not None else []


class Solution:
    def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:

        # we store the references here
        # key is the val
        # value is the list of neighbors (adjacency list)
        store = {}

        def recursiveCall(node: "Node") -> Optional["Node"]:
            # if this node is null
            if not node:
                return None

            # if this node exists but has no neighbors
            if node and not node.neighbors:
                return Node(node.val, [])

            # the node exists
            # create a new node with the value
            # of the node that we must clone
            clone = Node(node.val)
            # add this node's reference to the `Map`
            store[clone.val] = clone

            # start processing neighbors
            for neighbor in node.neighbors:
                # if we see a neighbor that's not already processed
                if neighbor.val not in store:
                    # first finish processing the neighbor recursively
                    store[neighbor.val] = recursiveCall(neighbor)  # type: ignore
                # pass that processed neighbor into the 
                # neighbors list of the original node we were processing
                clone.neighbors.append(store[neighbor.val])  # type: ignore

            # return the completed clone
            return clone

        # the initial call that triggers everything
        # if the node is not null
        if node:
            return recursiveCall(node)
        # if it's null return None
        else:
            return None

Complexity

  • Time: $O(n)$
    Since we process atmost $n$ nodes.

  • Space: $O(n)$
    Since we use a recursion stack that has atmost $n$ nodes in it.

Mistakes I Made

It took me a long while to understand what the question actually meant. I understood the part about “return a deep copy”, but after that I was just at a loss. Had to sleep on it.

And we are done.