Clone Graph - Leetcode Solution

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

        start = node
        o_to_n = {}
        stk = [start]
        visited = set()
        visited.add(start)

        while stk:
            node = stk.pop()
            o_to_n[node] = Node(val=node.val)

            for nei in node.neighbors:
                if nei not in visited:
                    visited.add(nei)
                    stk.append(nei)

        for old_node, new_node in o_to_n.items():
            for nei in old_node.neighbors:
                new_nei = o_to_n[nei]
                new_node.neighbors.append(new_nei)

        return o_to_n[start]

# Time Complexity: O(V+E)
# Space Complexity: O(V)

                

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
using namespace std;


class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;

        unordered_map<Node*, Node*> oToN;
        stack<Node*> stk;
        unordered_set<Node*> visited;

        stk.push(node);
        visited.insert(node);

        // DFS to create the nodes
        while (!stk.empty()) {
            Node* curr = stk.top();
            stk.pop();
            oToN[curr] = new Node(curr->val);

            for (Node* nei : curr->neighbors) {
                if (visited.find(nei) == visited.end()) {
                    visited.insert(nei);
                    stk.push(nei);
                }
            }
        }

        // DFS to set up neighbors
        for (auto& entry : oToN) {
            Node* oldNode = entry.first;
            Node* newNode = entry.second;
            for (Node* nei : oldNode->neighbors) {
                newNode->neighbors.push_back(oToN[nei]);
            }
        }

        return oToN[node];
    }
};

                

import java.util.*;

public class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;

        Map<Node, Node> oToN = new HashMap<>();
        Stack<Node> stk = new Stack<>();
        Set<Node> visited = new HashSet<>();

        stk.push(node);
        visited.add(node);

        // DFS to create the nodes
        while (!stk.isEmpty()) {
            Node curr = stk.pop();
            oToN.put(curr, new Node(curr.val));

            for (Node nei : curr.neighbors) {
                if (!visited.contains(nei)) {
                    visited.add(nei);
                    stk.push(nei);
                }
            }
        }

        // DFS to set up neighbors
        for (Map.Entry<Node, Node> entry : oToN.entrySet()) {
            Node oldNode = entry.getKey();
            Node newNode = entry.getValue();
            for (Node nei : oldNode.neighbors) {
                newNode.neighbors.add(oToN.get(nei));
            }
        }

        return oToN.get(node);
    }
}



                

/**
 * Definition for a Node.
 * function Node(val, neighbors) {
 *     this.val = val;
 *     this.neighbors = neighbors === undefined ? [] : neighbors;
 * }
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    if (!node) return null;

    const oToN = new Map();
    const stk = [node];
    const visited = new Set();

    visited.add(node);

    // DFS to create the nodes
    while (stk.length > 0) {
        const curr = stk.pop();
        oToN.set(curr, new Node(curr.val));

        for (const nei of curr.neighbors) {
            if (!visited.has(nei)) {
                visited.add(nei);
                stk.push(nei);
            }
        }
    }

    // DFS to set up neighbors
    for (const [oldNode, newNode] of oToN.entries()) {
        for (const nei of oldNode.neighbors) {
            newNode.neighbors.push(oToN.get(nei));
        }
    }

    return oToN.get(node);
};