Meta — Clone Graph (Deep Copy with DFS and HashMap)

Problem Statement#

Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains a value and a list of neighbors. The graph has no self-loops or duplicate edges.

Constraints:

• Number of nodes: 0 to 100
• 1 <= Node.val <= 100
• Node.val is unique for each node
• The graph is connected

Input:  adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: Deep copy of same graph structure

Input:  adjList = [[]]
Output: Single node with empty neighbor list

Why This Problem Matters#

Clone Graph (LeetCode 133) is a Meta interview staple that tests deep copy semantics and cycle detection in recursive data structures. At Meta, this problem is a proxy for cloning React component trees, duplicating social graph subgraphs for A/B testing, or deep-copying VR scene graphs in Oculus. Engineers who do not understand deep copy vs shallow copy make subtle bugs at scale.

The core challenge: a graph may have cycles. If you clone node A which has a neighbor B, and B has a neighbor back to A, a naive recursive clone would loop infinitely. The HashMap (old_node -> cloned_node) breaks cycles by returning the already-cloned node when revisiting a node.

Amazon, Google, and Microsoft also ask this. It is the foundation for "copy linked list with random pointer" (LeetCode 138) and "serialize/deserialize a graph" — all require the same visited-map pattern.

The Core Insight#

Maintain a hashmap cloned = {original_node: cloned_node}. DFS from the start node:

1. If the node is already in cloned, return the cloned copy (handles cycles and revisits)
2. Create a new node with the same value
3. Add it to cloned BEFORE recursing on neighbors (prevents infinite loops)
4. For each neighbor, recursively clone and add to the new node's neighbor list

The order matters: insert into the map before recursing, otherwise cycles cause infinite recursion.

Visual Dry Run#

Graph: 1-2, 1-4, 2-3, 3-4 (cycle: 1-2-3-4-1)

Solution (Optimal)#

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
 
class Solution:
    def cloneGraph(self, node) -> 'Node':
        if not node:
            return None
 
        cloned = {}
 
        def dfs(n):
            if n in cloned:
                return cloned[n]
            clone = Node(n.val)
            cloned[n] = clone  # insert BEFORE recursing
            for neighbor in n.neighbors:
                clone.neighbors.append(dfs(neighbor))
            return clone
 
        return dfs(node)

var cloneGraph = function(node) {
    if (!node) return null;
 
    const cloned = new Map();
 
    function dfs(n) {
        if (cloned.has(n)) return cloned.get(n);
        const clone = { val: n.val, neighbors: [] };
        cloned.set(n, clone);  // insert BEFORE recursing
        for (const neighbor of n.neighbors) {
            clone.neighbors.push(dfs(neighbor));
        }
        return clone;
    }
 
    return dfs(node);
};

Time: O(V + E) — visit each vertex and edge exactly once Space: O(V) — hashmap stores one entry per node; O(V) recursion stack in worst case

Common Mistakes#

• Inserting the cloned node into the map AFTER recursing on neighbors — causes infinite loop on cycles
• Using node value as the hashmap key instead of the node object — fails when two nodes have the same value
• Not returning the cloned node from the hashmap on revisit — creates duplicate cloned nodes
• Forgetting the null/None check for the empty graph case
• Using BFS but not initializing the queue with the start node's clone — misses the first node

Interview Tips#

• State the cycle problem immediately: "Without a visited map, cycles cause infinite recursion"
• Emphasize the insertion-before-recursion order — this is the critical detail Meta checks
• Offer both DFS (recursive) and BFS (iterative) approaches — show awareness of stack overflow risk for deep graphs
• Use the actual node object as the hashmap key, not node.val — Meta interviewers check for this
• The pattern generalizes: "copy any graph-like structure with cycles" uses the same visited-map approach

Follow-up Questions#

• How do you clone a linked list with random pointers? — Same hashmap pattern; two-pass or one-pass with map
• How would you implement this iteratively (BFS)? — Queue with a map; pop node, clone neighbors, add to queue
• What if the graph is disconnected? — The given problem guarantees connectivity; for disconnected, iterate over all nodes
• How do you deep copy a binary tree? — Same recursion but no cycles; no need for the visited map
• What if nodes have custom attributes? — Clone all attributes in the node constructor; same recursion structure

Key Takeaways#

• The hashmap {original_node: cloned_node} is the cycle-breaking mechanism for graph deep copy
• Insert the cloned node into the map BEFORE recursing on neighbors to prevent infinite loops on cycles
• Use the node object as the key, not the value — node values may not be unique in general graphs
• Time is O(V+E): each vertex visited once, each edge traversed once
• Meta tests this to verify understanding of deep copy semantics and cycle detection in recursive structures
• The same pattern applies to: copy linked list with random pointer, serialize a graph, clone N-ary trees
• BFS alternative uses a queue and the same map; preferred when recursion depth (V) might cause stack overflow