algoadvance

Leetcode 133. Clone Graph

Problem Statement

You are given a reference to a node in a connected undirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

Constraints:

Clarifying Questions

  1. Input Format: Is the input guaranteed to be a valid connected undirected graph?
    • Yes, the graph is always connected, and each node’s value is unique.
  2. Output Requirements: Should we return a reference to the node for the deep copy graph?
    • Yes, a reference to the node in the deep-cloned graph should be returned.
  3. Edge Cases: How should the function behave when the graph has zero nodes?
    • If the graph has zero nodes, we should return nullptr.

Strategy

The problem requires creating a deep copy of a graph. Each node in the graph is referenced by pointers in a vector of neighbors. We will use Depth-First Search (DFS) along with a hash map to keep track of already cloned nodes to avoid cycles and ensure each node is only cloned once.

Steps:

  1. Use a Hash Map: Maintain a hash map where the key is the original node and the value is the cloned node. This will help in checking if a node has already been cloned.
  2. DFS or BFS: Deep clone the graph using DFS or BFS.
  3. Handle Neighbors: For each node, recurse through each of its neighbors, clone them if they haven’t been cloned, and add the cloned neighbors to the new node’s neighbors list.
  4. Return the Cloned Graph: Finally, return the clone of the starting node.

Code

Here’s a concise C++ solution using DFS:

#include <unordered_map>
#include <vector>

using namespace std;

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

class Solution {
private:
    unordered_map<Node*, Node*> clonedNodes;
    
    Node* cloneGraphHelper(Node* node) {
        if(!node) return nullptr;

        // If node is already cloned, return cloned node
        if(clonedNodes.find(node) != clonedNodes.end()) {
            return clonedNodes[node];
        }

        // Clone the current node
        Node* clonedNode = new Node(node->val);
        clonedNodes[node] = clonedNode;

        // Recursively clone the neighbors
        for(Node* neighbor : node->neighbors) {
            clonedNode->neighbors.push_back(cloneGraphHelper(neighbor));
        }

        return clonedNode;
    }

public:
    Node* cloneGraph(Node* node) {
        return cloneGraphHelper(node);
    }
};

Time Complexity

The time complexity of this solution is (O(N + E)), where (N) is the number of nodes and (E) is the number of edges. This is because each node and edge are visited once during the DFS traversal.

This approach ensures a deep copy of the graph while maintaining efficiency.

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