SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem involves cloning an undirected graph. Each node in the graph contains a value and a list of its neighbors. Given a reference to a node in the graph, we need to create a deep copy of the graph and return the reference to the cloned node.

Intuition

The graph can be represented using a depth-first search (DFS) or breadth-first search (BFS) traversal. During the traversal, each node can be cloned, and its neighbors can be recursively cloned. Using a dictionary to map original nodes to their clones ensures that each node is cloned only once and helps to avoid infinite recursion for cyclic graphs.

Approach

1. Check if the Input Node is Null: If the input node is null, return null immediately since there is nothing to clone.
2. Initialize a Dictionary: Use a dictionary to map each original node to its cloned counterpart.
3. Define a DFS Function: This function will take a node and perform the following steps:
   • If the node has already been cloned (exists in the dictionary), return the clone.
   • Otherwise, create a new node (clone) with the same value as the original node and add it to the dictionary.
   • Iterate over the neighbors of the original node, recursively clone them, and add them to the neighbors of the cloned node.
4. Start the DFS: Call the DFS function with the input node and return the result.

Complexity

Time Complexity:

O(N + E), where N is the number of nodes and E is the number of edges in the graph. Each node and each edge is visited once during the DFS traversal.

Space Complexity:

O(N), where N is the number of nodes in the graph. This is due to the extra space used by the dictionary to store the mapping from original nodes to their clones, and the recursion stack.

Code

C++

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        
        unordered_map<Node*, Node*> oldToNew;
        
        return dfs(node, oldToNew);
    }
private:
    Node* dfs(Node* node, unordered_map<Node*, Node*>& oldToNew) {
        if (oldToNew.find(node) != oldToNew.end()) {
            return oldToNew[node];
        }
        Node* copy = new Node(node->val);
        oldToNew[node] = copy;
        
        for (Node* neighbor : node->neighbors) {
            copy->neighbors.push_back(dfs(neighbor, oldToNew));
        }
        return copy;
    }
};

Python

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

        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

        return dfs(node)

Java

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Map<Node, Node> oldToNew = new HashMap<>();
        
        return dfs(node, oldToNew);
    }
    private Node dfs(Node node, Map<Node, Node> oldToNew) {
        if (oldToNew.containsKey(node)) {
            return oldToNew.get(node);
        }
        Node copy = new Node(node.val);
        oldToNew.put(node, copy);
        
        for (Node neighbor : node.neighbors) {
            copy.neighbors.add(dfs(neighbor, oldToNew));
        }
        return copy;
    }
}

JavaScript

var cloneGraph = function (node) {
    let oldToNew = new Map();
    return node ? dfs(node) : null;

    function dfs(node) {
        if (oldToNew.has(node)) {
            return oldToNew.get(node);
        }

        let copy = new _Node(node.val);
        oldToNew.set(node, copy);

        for (let nei of node.neighbors) {
            copy.neighbors.push(dfs(nei));
        }
        return copy;
    }
};