We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Clone Graph

Number: 133

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Google, Microsoft, Grammarly, ThousandEyes, Adobe, eBay, Apple, Docusign, TikTok, Pocket Gems, Uber, Wix

Problem Description

Given a reference to a node in a connected undirected graph where every node has a unique integer value and a list of its neighbors, return a deep copy (clone) of the entire graph. The graph is represented as an adjacency list and the given node is guaranteed to have its value as 1 if the graph is not empty.

Key Insights

  • The graph is undirected and connected.
  • Each node must be cloned exactly once to prevent cycles and repetitions.
  • Use a mapping/dictionary to keep track of cloned nodes.
  • A depth-first search (DFS) or breadth-first search (BFS) can be used to traverse and clone the graph.
  • Handle edge cases where the graph might be empty.

Space and Time Complexity

Time Complexity: O(N + E), where N is the number of nodes and E is the number of edges, because each node and each edge are traversed once.

Space Complexity: O(N), to store the mapping from original nodes to their clones, and for the recursion/queue used in traversal.

Solution

We employ a depth-first search (DFS) approach to clone the graph. The main idea is to create a mapping (hash table) that links each original node to its corresponding cloned node. During the DFS traversal, if a node is encountered for the first time, a new node is created and stored in the mapping; then, the algorithm recursively clones all of its neighbors. For an already visited node, the cloned node is directly returned from the mapping. This ensures that every node is cloned only once and correctly handles cycles in the graph.

Code Solutions

Below are the code solutions in Python, JavaScript, C++, and Java with line-by-line comments:

# Definition for a Node.
class Node:
    def __init__(self, val, neighbors=None):
        self.val = val
        # Initialize neighbors with empty list if None is provided
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node: 'Node') -> 'Node':
    # Hash map to track original nodes and their corresponding clones
    old_to_new = {}

    def dfs(current):
        # Base case: if the current node is None, return None
        if current is None:
            return None
        # If the node has already been cloned, return the clone to avoid duplication and cycle issues
        if current in old_to_new:
            return old_to_new[current]
        # Create a clone for the current node
        copy = Node(current.val)
        old_to_new[current] = copy
        # Recursively clone all neighbors
        for neighbor in current.neighbors:
            copy.neighbors.append(dfs(neighbor))
        return copy

    return dfs(node)
← Back to All Questions