DevExCode

LeetCode 133: Clone Graph Solution

Master LeetCode problem 133 (Clone Graph), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To clone a graph, we can perform a depth-first search (DFS) traversal of the original graph while creating copies of the nodes and their neighbors in the new graph. We can use a hashmap to keep track of the nodes we have already cloned to avoid duplicating nodes.

  1. Create a hashmap to store the mapping between original nodes and their corresponding clones.
  2. Start DFS traversal from the given node.
  3. For each neighbor of the current node, check if it has already been cloned. If not, create a clone and recursively call the DFS function on the neighbor.
  4. Return the clone of the given node.

The time complexity of this approach is O(V + E), where V is the number of nodes and E is the number of edges in the graph. The space complexity is also O(V) to store the mapping between nodes.

Solution Code

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

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 133 (Clone Graph)?

This page provides optimized solutions for LeetCode problem 133 (Clone Graph) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 133 (Clone Graph)?

The time complexity for LeetCode 133 (Clone Graph) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 133 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 133 in Java, C++, or Python.

Back to LeetCode Solutions