Leetcode 133: Clone Graph

Input: The input is a graph represented by an adjacency list, where each list describes the neighbors of a node.

Example: [[2,4],[1,3],[2,4],[1,3]]

Constraints:

• 0 <= adjList.length <= 100

• Each node in the graph is unique.

• There are no repeated edges or self-loops in the graph.

Output: The output is the deep copy of the graph starting from the given node.

Example: [[2,4],[1,3],[2,4],[1,3]]

Constraints:

• The output will be the same structure as the input graph, but with distinct node objects.

Goal: The goal is to create a deep copy of the graph by copying each node and its neighbors while ensuring that no node is visited more than once.

Steps:

• 1. Create a hashmap to store copies of each node as they are encountered.

• 2. Use a recursive approach to visit each node and copy it.

• 3. For each node, create a new copy and recursively copy its neighbors.

Goal: The input graph has no self-loops or duplicate edges, and the graph is always connected.

Steps:

• 1 <= Node.val <= 100

• The graph will always be connected.

Assumptions:

• The graph is always connected.

• There are no duplicate edges or self-loops.

• Input: [[2,4],[1,3],[2,4],[1,3]]

• Explanation: The graph has 4 nodes and 4 edges, where each node is connected to its respective neighbors.

• Input: [[]]

• Explanation: This graph consists of a single node with no neighbors.

Approach: The solution uses a depth-first search (DFS) approach, leveraging recursion and a hashmap to track visited nodes and avoid revisiting nodes during the copy process.

Observations:

• We need to create a new node for each existing node in the graph.

• We need to ensure that we don't revisit nodes that have already been copied.

• A recursive DFS approach will be efficient for this problem as we need to traverse the entire graph and copy each node and its neighbors.

Steps:

• 1. Define a hashmap to store copies of nodes by their value.

• 2. Implement a recursive function that, for each node, copies the node and recursively copies its neighbors.

• 3. Ensure each node is copied only once by checking the hashmap before creating a new copy.

Empty Inputs:

• If the input graph is empty, return an empty list.

Large Inputs:

• The solution should handle up to 100 nodes and avoid stack overflow or memory issues.

Special Values:

• If the graph contains only one node, return a copy of that single node with no neighbors.

Constraints:

• The graph is always connected, so no need to handle disconnected graphs.

map<int, Node*> mp;
Node* cloneGraph(Node* node) {
    if(node == NULL) return node;
    Node * ans;
    ans = copy(node);
    return ans;
}

Node* copy(Node* node) {
    if(mp.count(node->val)) return mp[node->val];
    Node* ans = new Node(node->val);
    mp[node->val] = ans;
    for(auto it: node->neighbors) {
        Node* n = copy(it);
        ans->neighbors.push_back(n);
    }
    return ans;
}

1 : Map Insertion

map<int, Node*> mp;

Declare a map to store the copied nodes. The key is the node's value, and the value is the node object itself.

2 : Function Definition

Node* cloneGraph(Node* node) {

Define the function `cloneGraph` that takes a `Node` pointer and returns a cloned graph.

3 : Null Check

    if(node == NULL) return node;

Check if the input node is NULL. If it is, return NULL as there is nothing to clone.

4 : Variable Declaration

    Node * ans;

Declare a pointer `ans` which will store the cloned graph.

5 : Function Call

    ans = copy(node);

Call the helper function `copy` to clone the graph starting from the given node.

6 : Return Statement

    return ans;

Return the cloned graph.

7 : Helper Function Definition

Node* copy(Node* node) {

Define the helper function `copy` that clones the graph recursively.

8 : Map Lookup

    if(mp.count(node->val)) return mp[node->val];

Check if the node has already been cloned (present in the map). If it is, return the existing clone.

9 : Node Creation

    Node* ans = new Node(node->val);

Create a new node with the same value as the input node.

10 : Map Insertion

    mp[node->val] = ans;

Insert the new node into the map to store it for future reference.

11 : Graph Traversal

    for(auto it: node->neighbors) {

Loop through each neighbor of the current node to clone them.

12 : Recursive Call

        Node* n = copy(it);

Recursively call `copy` on each neighbor to clone it.

13 : List Insertion

        ans->neighbors.push_back(n);

Add the cloned neighbor to the `neighbors` list of the current cloned node.

14 : Return Statement

    return ans;

Return the cloned node after its neighbors have been cloned and added.

Best Case: O(N), where N is the number of nodes in the graph.

Average Case: O(N + E), where E is the number of edges in the graph, as every edge needs to be visited once.

Worst Case: O(N + E), where N is the number of nodes and E is the number of edges.

Description: The time complexity is linear in terms of nodes and edges because we traverse each node and each edge once.

Best Case: O(N), as we store a copy of each node in the hashmap.

Worst Case: O(N), where N is the number of nodes, for the space used by the recursive stack and the hashmap storing copies of the nodes.

Description: The space complexity is O(N) due to the storage requirements for the copied nodes and the recursion stack.

Leetcode 133: Clone Graph

Solution to LeetCode 133: Clone Graph Problem

Explore →