Clone Graph

Medium

Apple

5 views

Topics:

Graphs

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 (int) and a list (List[Node]) of its neighbors.

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

For simplicity, each node's value is the same as the node's index (1-indexed). The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]]

Explanation: There are 4 nodes in the graph.

1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

Input: adjList = [[]] Output: [[]] Explanation: The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = [] Output: [] Explanation: This an empty graph, it does not have any nodes.

Constraints:

The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
Node.val is unique for each node.
There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.

Clone Graph

Medium

Apple

5 views

Topics:

Graphs

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 (int) and a list (List[Node]) of its neighbors.

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

For simplicity, each node's value is the same as the node's index (1-indexed). The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]]

Explanation: There are 4 nodes in the graph.

1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

Input: adjList = [[]] Output: [[]] Explanation: The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = [] Output: [] Explanation: This an empty graph, it does not have any nodes.

Constraints:

The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
Node.val is unique for each node.
There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the graph be empty, and if so, what should I return?
Are the node values guaranteed to be unique, and are they always integers?
Is the graph guaranteed to be connected, or could it contain disconnected components?
Does the input graph contain cycles?
Should the cloned graph maintain the same adjacency list order as the original graph?

Brute Force Solution

Approach

The goal is to create a complete copy of a graph. A brute force approach involves exploring every possible node and connection, systematically building the copy until it mirrors the original.

Here's how the algorithm would work step-by-step:

Start by creating a brand new node to represent the first node in the original graph.
Then, look at all the nodes that are connected to the first node in the original graph.
For each of those connected nodes, create a new node in your copy, if a copy of the connected node doesn't already exist.
After creating or finding copies of all the directly connected nodes, connect the new nodes in the copied graph the same way the original nodes are connected.
Repeat this process for each node you've created in your copied graph, making sure to check all of their connections and creating new nodes as needed if a copy doesn't exist.
Keep going until you've visited every node in the original graph and ensured all its connections have been recreated in the copied graph.
The result is a completely new graph that looks exactly like the original, but is stored separately.

Code Implementation

def clone_graph(node):
    if not node:
        return None

    # Use a dictionary to store the mapping from original nodes to cloned nodes
    node_map = {}

    # Create a clone of the first node
    cloned_node = Node(node.val)
    node_map[node] = cloned_node

    queue = [node]

    while queue:
        original_node = queue.pop(0)

        # Iterate through the neighbors of the current node
        for neighbor in original_node.neighbors:
            # If the neighbor has not been cloned yet
            if neighbor not in node_map:
                # Create a clone of the neighbor
                cloned_neighbor = Node(neighbor.val)
                node_map[neighbor] = cloned_neighbor
                queue.append(neighbor)

            # Add the cloned neighbor to the neighbors of the cloned node
            node_map[original_node].neighbors.append(node_map[neighbor])

    return cloned_node

class Node:
    def __init__(self, val, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

Big(O) Analysis

Time Complexity

O(n+m) – The algorithm visits each of the n nodes in the graph. For each node, it iterates through its neighbors. The total number of neighbor visits across all nodes is equal to the number of edges, m. Therefore, the time complexity is proportional to the sum of the number of nodes and the number of edges, resulting in O(n+m).

Space Complexity

O(N) – The algorithm uses a hash map (or dictionary) to store the mapping between original nodes and their cloned counterparts. In the worst-case scenario, where the graph is fully connected and every node is visited, the hash map will contain entries for all N nodes of the graph. Therefore, the auxiliary space required for the hash map grows linearly with the number of nodes in the graph. Consequently, the space complexity is O(N).

Optimal Solution

Approach

We want to make a perfect copy of a connected group of objects. The clever trick is to keep track of the objects we've already copied so we don't waste time re-copying them.

Here's how the algorithm would work step-by-step:

Start with the first object in the group.
Make a copy of this object. If we've already made a copy, don't make another one; just use the copy we made before.
Look at the objects connected to the first object. For each of these connected objects, make a copy (unless we already have one).
Now, connect the copy of the first object to the copies of its connected objects.
Repeat this process for each object we encounter, always making sure we only copy an object once and that we correctly connect all the copies together.
Continue until we have visited and copied every object in the group and all connections are duplicated.

Code Implementation

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node: 'Node') -> 'Node':
    if not node:
        return None

    cloned_nodes = {}

    def clone_node(node):
        if node in cloned_nodes:
            return cloned_nodes[node]

        # Create a clone for the current node
        cloned_node = Node(node.val)
        cloned_nodes[node] = cloned_node
        return cloned_node

    cloned_starting_node = clone_node(node)
    queue = [node]
    visited_nodes = {node}

    while queue:
        current_node = queue.pop(0)
        current_cloned_node = cloned_nodes[current_node]

        for neighbor_node in current_node.neighbors:
            cloned_neighbor_node = clone_node(neighbor_node)

            # Connect cloned node to its cloned neighbors
            current_cloned_node.neighbors.append(cloned_neighbor_node)

            # Avoid infinite loops by only visiting each node once.
            if neighbor_node not in visited_nodes:
                queue.append(neighbor_node)
                visited_nodes.add(neighbor_node)

    return cloned_starting_node

Big(O) Analysis

Time Complexity

O(V + E) – The algorithm visits each node (vertex) in the graph once. Let V be the number of vertices. For each node, it iterates through its neighbors (edges). Let E be the number of edges. The cloning process involves creating new nodes and copying the adjacency list, but each node and edge is processed at most once. Therefore, the time complexity is proportional to the number of vertices plus the number of edges, or O(V + E).

Space Complexity

O(N) – The algorithm uses a hash map (or dictionary) to store the mapping between original nodes and their cloned counterparts. In the worst-case scenario, we need to clone all N nodes in the graph, leading to N entries in the hash map. Additionally, a queue (implicitly used by the process of 'visiting and copying every object') to manage the nodes to be visited can also hold up to N nodes in the worst case (when all nodes are connected). Thus the auxiliary space is proportional to the number of nodes, which simplifies to O(N).

Edge Cases

Case	How to Handle
Null input graph	Return null immediately indicating no graph to clone.
Empty graph (graph with no nodes)	Return null, representing an empty clone.
Graph with a single node	Create a new node with the same value and return it.
Graph with multiple nodes and cycles	Use a visited set (or map) to prevent infinite recursion or loops during the graph traversal and cloning.
Disconnected graph (multiple components)	The algorithm should correctly clone each disconnected component.
Graph with a large number of nodes (scalability)	Ensure the algorithm uses iterative traversal (BFS or DFS) instead of recursion to avoid stack overflow errors, and that the space complexity is O(N) where N is the number of nodes.
Self-loop (node connected to itself)	The algorithm should correctly clone the self-loop connection when creating the new node's neighbors.
Nodes with different data types	Assume that all node values are of the same comparable type; otherwise, type handling logic would need to be added.