Deep cloning — leetcode

Hey, I am back and I would like to continue my useless blog about leetcode tasks analysis.

Today I will cover medium task from graph section: Clone graph

The task is pretty simple to make a deep clone of original graph. But what is deep clone? As far as I understood, its just creating the same item. In simple words, you found a song in internet which you can play.

Imagine, you saved a link on your computer, its not deep clone, as if the original song from website is changed somehow, you will get changed version of the song via your saved link as well.

If you make a record of this sond using your voice, it will not be deep clone as well. Original and saved record will have the same words, but different sound due to your voice.

But if you save the sond on your PC fully as mp3 file, we can consider it as deep clone. The song is the same which you have in internet, BUT its other new object and there is no link with original one. So, changes of the song from website will not change your saved mp3 file on your PC.

Come back to the task. I will not do too much explanations.

Below piece of code is available from leetcode itself for our information and we can use it to run the task on our machines

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

Then we have to create a input for our function. Create 4 nodes and then assing relations between nodes via *.neighbors

node_1 = Node(1)
node_2 = Node(2)
node_3 = Node(3)
node_4 = Node(4)

node_1.neighbors = [node_2, node_4]
node_2.neighbors = [node_1, node_3]
node_3.neighbors = [node_2, node_4]
node_4.neighbors = [node_1, node_3]

Then we have to define set of nodes which will be cloned and main function which is responsible for deep cloning. The logic of method is simple. If input node already exists in oldToNew set, then we can stop recursive cloning process. If not, create new node with the same value as original node, add it to set of cloned nodes and go through all existed neighbors with recoursive calling the same function.

So, in case of below graph we have to follow the next steps:

1. Node #1 -> add to the node list -> look at Neighbor — Node #2 -> call the same method -> Node #2 -> add to the node list -> look at Neighbor — Node #3 -> call the same method -> Node #4 -> add to the node list -> look at Neighbor — Node #1 -> Wow! Node #1 is already exist in the node list.
2. Then check other Neighbor — Node #3 -> Its also in the list already -> then check Neighbor — Node #2 -> Its in the list as well. Then check neighbor — Node #1 and then do the same for Neighbor — Node#4.

The idea is pretty the same as passing labyrinth by left hand.

def dfs(node):
    if node in oldToNew:
        return oldToNew[node]

    copy = Node(node.val)
    oldToNew[node] = copy
    for neighbor in node.neighbors:
        copy.neighbors.append(dfs(neighbor))
    return copy

And as result, we have to return clone of input graph.

Full solution:

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

node_1 = Node(1)
node_2 = Node(2)
node_3 = Node(3)
node_4 = Node(4)

node_1.neighbors = [node_2, node_4]
node_2.neighbors = [node_1, node_3]
node_3.neighbors = [node_2, node_4]
node_4.neighbors = [node_1, node_3]

oldToNew = {}

def dfs(node):
    if node in oldToNew:
        return oldToNew[node]

    copy = Node(node.val)
    oldToNew[node] = copy
    for neighbor in node.neighbors:
        copy.neighbors.append(dfs(neighbor))
    return copy

result = dfs(node_1) if node_1 else None
return result

Thanks