algoadvance

Leetcode 133. Clone Graph

Problem Statement

The problem “133. Clone Graph” on LeetCode is as follows:

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value (val) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

Clarifying Questions

1. Graph Properties: Is it guaranteed that the graph is connected and undirected?
   • Yes, the problem states the graph is connected and undirected.
2. Node Values: Are the node values unique?
   • While the problem does not explicitly state that the val is unique, we will assume it for simplicity in cloning the graph.
3. Input Form: How is the input graph going to be provided?
   • The input is a reference to a Node object, which is assumed to be the root node of the graph.
4. Empty Graph: How should we handle an empty graph (i.e., when the input node is null)?
   • If the input node is null, we should return null.

Strategy

To deep clone the graph, we will use Depth-First Search (DFS) approach with a hashmap to store the original nodes and their corresponding cloned nodes. This ensures we map each original node to its clone and avoid duplication.

Here is a step-by-step strategy:

1. Handle Special Case: If the input node is null, return null.
2. Use a HashMap: Create a hashmap to store the mapping from original nodes to their cloned counterparts.
3. Clone Using DFS: Implement a DFS function which will:
   • Check if the node has already been cloned. If yes, return the cloned node.
   • If not, create a new node.
   • Clone all the neighbors recursively.
   • Add the node to the hashmap to mark it as cloned.

Code

import java.util.*;

class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class Solution {
    private Map<Node, Node> map = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        return clone(node);
    }

    private Node clone(Node node) {
        if (map.containsKey(node)) {
            return map.get(node);
        }

        Node cloneNode = new Node(node.val, new ArrayList<>());
        map.put(node, cloneNode);

        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(clone(neighbor));
        }

        return cloneNode;
    }
}

Time Complexity

• Time Complexity: The time complexity is (O(V + E)), where (V) is the number of vertices (nodes) and (E) is the number of edges. This is because each node and each edge is visited once.

• Space Complexity: The space complexity is (O(V)). This accounts for the space used by the HashMap and the recursion stack in the DFS.

This solution ensures that every node and its corresponding edges are cloned exactly once, preserving the original graph structure.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?