How to Solve: Clone a Graph – Complete Guide for FAANG Interviews

How to Solve: Clone a Graph – Complete Guide for FAANG Interviews

? Introduction

"This problem tests your ability to traverse and reconstruct a graph—if you nail it, you prove you can handle recursion, cycles, and deep copies, which are core skills for system design and distributed systems interviews at FAANG."

? WHAT YOU NEED TO KNOW FIRST

Before attempting this problem, you must understand: 1. Graph Traversal (DFS/BFS) – How to visit every node in a graph. 2. Hash Maps (Dictionaries) – For O(1) lookups and tracking visited nodes. 3. Recursion vs. Iteration – When to use each for graph traversal.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow these steps every time you solve a "Clone a Graph" problem:

1. Understand the Input & Output
2. Input: A Node (graph node with val and neighbors list).

3. Output: A deep copy of the entire graph (new nodes, not references).

4. Handle Edge Cases

5. If node is None, return None.

6. If the graph has only one node (no neighbors), return a new node with the same value.

7. Choose Traversal (DFS or BFS)

8. DFS (Recursive): Simpler to implement, but may hit recursion limits for very deep graphs.

9. BFS (Iterative): Better for wide graphs, avoids recursion stack issues.

10. Initialize a Visited Map

11. Key: Original node → Value: Cloned node.

12. Prevents cycles and redundant work.

13. Traverse & Clone Nodes

14. For each node, create a new node with the same val.

15. Store the mapping in visited.

16. Reconstruct Edges

17. For each neighbor of the original node, add the cloned neighbor to the new node’s neighbors list.

18. Return the Cloned Graph

19. The entry point is the cloned version of the input node.

? WORKED EXAMPLES

Example 1 – Basic (DFS Recursive)

Problem: Clone an undirected graph where each node has a val and a list of neighbors.

Solution:

class Node:

    def __init__(self, val=0, neighbors=None):

        self.val = val

        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node: 'Node') -> 'Node':

    if not node:

        return None


    visited = {}  # Maps original node → cloned node


    def dfs(original_node):

        if original_node in visited:

            return visited[original_node]


        # Clone the node

        clone = Node(original_node.val)

        visited[original_node] = clone


        # Clone all neighbors

        for neighbor in original_node.neighbors:

            clone.neighbors.append(dfs(neighbor))


        return clone


    return dfs(node)

Time Complexity: O(V + E) (visits every node and edge once). Space Complexity: O(V) (visited map + recursion stack).

Why This Works: - DFS ensures we visit every node exactly once. - The visited map prevents cycles and redundant cloning. - Recursion naturally handles the traversal order.

Example 2 – Medium (BFS Iterative)

Problem: Same as above, but implement it iteratively (BFS).

Solution:

from collections import deque

def cloneGraph(node: 'Node') -> 'Node':

    if not node:

        return None


    visited = {}

    queue = deque([node])

    visited[node] = Node(node.val)  # Clone the first node


    while queue:

        original_node = queue.popleft()


        for neighbor in original_node.neighbors:

            if neighbor not in visited:

                visited[neighbor] = Node(neighbor.val)  # Clone neighbor

                queue.append(neighbor)

            # Add the cloned neighbor to the current node's neighbors

            visited[original_node].neighbors.append(visited[neighbor])


    return visited[node]

Time Complexity: O(V + E) (same as DFS). Space Complexity: O(V) (visited map + queue).

Why This Works: - BFS avoids recursion stack limits. - The queue ensures we process nodes level by level. - The visited map still prevents cycles.

Example 3 – Hard (Follow-Up: Clone with Random Pointers)

Problem: Clone a graph where each node has a random pointer (like in "Copy List with Random Pointer").

Solution:

class Node:

    def __init__(self, val=0, neighbors=None, random=None):

        self.val = val

        self.neighbors = neighbors if neighbors is not None else []

        self.random = random

def cloneGraph(node: 'Node') -> 'Node':

    if not node:

        return None


    visited = {}


    def dfs(original_node):

        if original_node in visited:

            return visited[original_node]


        clone = Node(original_node.val)

        visited[original_node] = clone


        for neighbor in original_node.neighbors:

            clone.neighbors.append(dfs(neighbor))


        # Handle random pointer

        if original_node.random:

            clone.random = dfs(original_node.random)


        return clone


    return dfs(node)

Time Complexity: O(V + E) (same as before). Space Complexity: O(V) (visited map + recursion stack).

Why This Works: - The random pointer is treated like another neighbor. - DFS ensures all pointers (neighbors + random) are cloned correctly.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. To clone a graph, you need three things: a traversal method (DFS or BFS), a visited map to avoid cycles, and a way to reconstruct edges. Start by handling edge cases—empty graph, single node. Then, pick DFS or BFS. DFS is simpler, but BFS avoids recursion limits. Use the visited map to track cloned nodes. For each node, clone it, then clone its neighbors. Finally, reconnect the edges. Common pitfalls? Forgetting the visited map, shallow copying, or missing neighbors. If the interviewer throws in a random pointer, treat it like another neighbor. You’ve got this—now go ace that interview!

? Final Notes

• Practice: Implement both DFS and BFS versions.
• Test: Try cyclic graphs, disconnected graphs, and single-node graphs.
• Follow-Up: Be ready for variations (e.g., random pointers, weighted edges).

This framework ensures you never blank on a "Clone a Graph" problem in an interview. Good luck! ?