Clone Graph - Deep Copy of Connected Undirected Graph

The clone graph problem requires creating a deep copy of a connected undirected graph where each node must be duplicated while preserving all connections between nodes in the original structure.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we guaranteed that the graph is connected, or can it have multiple disconnected components?
2. Can the input graph contain cycles, and should we handle them properly during cloning?
3. What is the maximum number of nodes in the graph? (This helps determine if we need to worry about stack overflow or memory limits)
4. Should we mutate the input graph, or must we create a completely independent clone?
5. What is the expected time complexity for follow-up? O(n) or O(n log n) acceptable?

Restate the pattern or problem type in your own words: The clone graph problem asks us to create a deep copy of a connected undirected graph where each node has a value and a list of neighbors. The challenge is to ensure that we don't just copy references but create entirely new nodes with the same structure and relationships.

Clarify the signal words and constraint shape that point to it:

• "Clone" or "copy" of a graph structure
• Nodes with values and neighbor lists (typically represented as adjacency lists)
• Need to maintain the same topological structure in the new graph
• Graphs may contain cycles or self-loops

Note any assumptions you are making:

• The graph is connected (all nodes reachable from one another)
• Each node has a unique identifier/value
• The graph is undirected (if we were to make it directed, the approach would be similar but with directional edges)
• Nodes can have zero or more neighbors

Identify whether the pattern is best suited for static, streaming, or online scenarios if relevant: This pattern is primarily suited for static scenarios where the entire graph structure is known upfront. It's not typically used in streaming or online settings where nodes arrive dynamically, though the same principles can be extended to handle incremental graph building.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Clone" or "copy" operations on graph structures
• Graphs with nodes that have references to other nodes (directed or undirected)
• "Node with neighbors" or "adjacency list" structures
• Problems asking to create a deep copy while preserving the original structure

Why this pattern fits better than alternatives: This is fundamentally a graph traversal problem with the additional constraint of creating new nodes while maintaining the same structural relationships. Unlike simple tree cloning, graphs can have cycles and multiple references to the same node, requiring careful handling to avoid infinite loops and ensure each original node maps to exactly one cloned node.

Conditions where variations apply:

• If the graph is a tree (no cycles), we can use simpler DFS or BFS with no need for visited tracking
• If the graph is undirected and we're only concerned with structural equivalence, we might use a simpler approach without maintaining node mappings
• For streaming graphs where nodes arrive over time, we'd need a different approach than batch processing

Core insight: The key insight is that we must maintain a mapping between original nodes and their clones to handle cycles and ensure that when we encounter a node that was already cloned, we reuse the existing clone rather than creating a new one. This requires us to process nodes in a way that ensures we don't create duplicate nodes for the same original node.

This pattern is particularly effective when we can leverage hash maps to store the node-to-clone mapping, allowing O(1) lookup and ensuring we never process the same node twice in our traversal.

3. Approach Evolution

Interview communication script:

"My first instinct is to solve this using a depth-first search (DFS) approach because we need to traverse the entire graph structure and create copies of each node. But let me think about this more carefully - if I just do a simple DFS and copy nodes as I visit them, I might end up creating duplicate copies of the same node, especially when there are cycles in the graph.

Let me think about how to optimize this. The key insight is that I need to maintain a mapping between original nodes and their clones to avoid creating multiple copies of the same node. This is where I can reduce it from O(n²) to O(n) - by using a hash map to track already cloned nodes.

I notice that if I maintain a mapping from original nodes to their clones, and use that as an invariant throughout the traversal, I can ensure each node is cloned exactly once. This approach will be O(n + m) where n is the number of nodes and m is the number of edges, which is optimal for graph traversal problems."

Brute-force approach and why it is not ideal:

The brute-force approach would be to traverse the graph recursively without any memoization, copying each node as we encounter it. This leads to exponential time complexity because we might end up cloning the same nodes multiple times, especially in graphs with cycles. For example, if we have a cycle like A → B → C → A, we'd keep cloning node A repeatedly.

Improved approach and the key optimization:

The improved approach uses a hash map to maintain a mapping between original nodes and their clones. The key optimization is that we check if a node has already been cloned before creating a new copy. This ensures each node is processed exactly once, reducing time complexity from exponential to linear.

Final approach with step-by-step reasoning:

1. Use a hash map to store the mapping from original nodes to cloned nodes
2. For each node in the graph, if it hasn't been cloned yet:
   • Create a new node with the same value
   • Add it to the mapping
   • Recursively process all neighbors
3. For each neighbor, if already cloned, use the existing clone; otherwise create new clone and process it
4. This ensures we never create duplicate copies of the same node

Important invariants that must hold:

1. Each original node maps to exactly one clone node in the hash map
2. The cloned graph maintains the same structure as the original graph
3. No node is cloned more than once during traversal
4. All edges in the original graph are preserved in the cloned graph with correct references

4. Data Structure Choice

For the clone graph problem, I need to carefully select data structures that will support both the graph traversal and the cloning process efficiently.

Primary Data Structures:

1. HashMap<Node, Node> - This is the most critical data structure for this problem. I'll use it to map original nodes to their clones to avoid creating duplicate nodes and to handle cycles in the graph. The key insight is that when I encounter a node I've already processed, I should return the existing clone rather than creating a new one.

2. Queue/Stack for BFS/DFS traversal - I need some form of traversal structure to process nodes. I'll use a Queue for BFS approach, which naturally handles the breadth-first processing required to clone all neighbors before diving deeper.

Why Each Data Structure Is Needed:

The HashMap is essential because it serves as both a visited set (to track which nodes have been cloned) and a mapping structure (to associate original nodes with their clones). Without this, I'd have no way to reference already-created clones when processing neighbors.

The traversal structure (Queue) is needed for systematic graph exploration. In BFS, I process nodes level by level, ensuring that all neighbors of a node are handled before I move to deeper levels.

Time and Space Impact:

• HashMap: O(n) space for storing n nodes, O(1) average time for lookups and insertions
• Queue: O(w) space where w is the maximum width of the graph (at most n), O(1) for enqueue/dequeue operations

Helper Structure:

I don't need any additional helper structures beyond the HashMap for tracking visited nodes, since the HashMap itself serves that purpose by storing the cloned nodes. This avoids the need for a separate visited set and reduces space complexity.

The choice of HashMap over other structures like HashSet is crucial because I need to store and retrieve the mapping between original and cloned nodes, not just track visited status.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Example: Consider a graph with 3 nodes (1, 2, 3) where node 1 connects to node 2, and node 2 connects to node 3.

Step 1: Start with node 1. Create a clone of node 1 and add it to our map. Map: {originalNode1 → clonedNode1}

Step 2: Process neighbors of node 1. Node 1 connects to node 2, so we need to handle node 2.

Step 3: Check if node 2 exists in our map. It doesn't, so we create a clone of node 2 and add it to the map. Map: {originalNode1 → clonedNode1, originalNode2 → clonedNode2}

Step 4: Process neighbors of node 2. Node 2 connects to node 3.

Step 5: Check if node 3 exists in our map. It doesn't, so we create a clone of node 3 and add it to the map. Map: {originalNode1 → clonedNode1, originalNode2 → clonedNode2, originalNode3 → clonedNode3}

Step 6: Process neighbors of node 3. Node 3 has no neighbors, so we're done with that branch.

Step 7: Backtrack to node 2. We've already cloned its neighbor (node 3), so we connect the cloned node 2 to cloned node 3.

Step 8: Backtrack to node 1. We've already cloned its neighbor (node 2), so we connect the cloned node 1 to cloned node 2.

Step 9: The algorithm terminates when we've processed all nodes in the original graph. The cloned graph is now fully constructed with proper connections.

The key insight is that we maintain a mapping between original and cloned nodes to avoid creating duplicate clones, ensuring each node is processed exactly once. The DFS traversal ensures we explore all connected components of the graph.

This approach handles cycles correctly because once a node is cloned, we never reprocess it. The map acts as both a visited set and a way to reference existing clones when connecting neighbors.

6. Java Solution

// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class Solution {
    // Map to store the mapping from original node to cloned node
    private Map<Node, Node> visited = new HashMap<>();
    
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        
        // If we've already cloned this node, return the clone
        if (visited.containsKey(node)) {
            return visited.get(node);
        }
        
        // Create a new node with the same value
        Node clone = new Node(node.val);
        
        // Store the mapping before recursing to handle cycles
        visited.put(node, clone);
        
        // Clone all neighbors recursively
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }
        
        return clone;
    }
}

This solution uses a depth-first search approach with a hash map to track already cloned nodes. The key insight is to create clones lazily while maintaining the mapping to handle cycles in the graph structure. The visited map prevents infinite recursion and ensures each node is cloned exactly once.

7. Complexity Analysis

Time Complexity: O(N + M) where N is the number of nodes and M is the number of edges in the graph.

The algorithm visits each node exactly once during the DFS traversal, and for each node, it processes all of its neighbors. Since we're traversing each edge exactly twice (once from each endpoint), the total work is proportional to the number of nodes plus the number of edges.

Space Complexity: O(N) for the HashMap storing the cloned nodes and the recursion stack in the worst case.

The HashMap requires O(N) space to store the mapping from original nodes to cloned nodes. In the worst case (a linear chain of nodes), the recursion stack depth could be O(N). For a balanced tree structure, the stack depth would be O(log N), but we must account for the worst-case scenario.

Why these bounds are correct:

The time complexity is optimal because we must examine each node and edge at least once to create a proper clone. Any attempt to skip nodes or edges would result in an incomplete graph copy.

The space complexity is tight because:

1. The HashMap is necessary to avoid infinite loops in cyclic graphs
2. The recursion stack depth is bounded by the graph's structure, with the worst case being a linear chain
3. We don't need additional space for edge tracking since we're only concerned with node cloning

This solution is optimal in both time and space for the graph cloning problem, as we cannot avoid visiting each node and edge at least once, and we must store references to all cloned nodes to handle cycles correctly.

8. Edge Cases & Pitfalls

Empty and minimal inputs

• Empty graph: When the input node is null, the result should also be null
• Single node: A graph with just one node (no neighbors) must be handled correctly to avoid infinite loops
• Self-referencing: A node that points to itself creates a cycle that must be detected and handled properly

Duplicate values and repeated states

• Duplicate node values: Multiple nodes can have the same value, but they must be distinct objects in memory
• Cyclic references: The graph can contain cycles where a path leads back to a previously visited node
• Multiple references to same node: Different nodes may reference the same cloned node, requiring proper deduplication

Boundary conditions

• Null neighbors: Nodes may have null neighbor lists or individual null neighbors in the list
• Deep nesting: Very deeply nested graphs (e.g., chains of 1000+ nodes) can cause stack overflow in recursive approaches
• Large graphs: Memory constraints when cloning very large graphs

Common implementation mistakes

• Not tracking visited nodes: Without proper tracking, recursive solutions can infinitely loop on cyclic graphs
• Modifying original graph: Attempting to clone by modifying the original node's neighbor list instead of creating new nodes
• Incorrect mapping: Using value-based lookup instead of object identity for the clone mapping, causing wrong references
• Stack overflow: Using naive recursion without proper base case handling for deep graphs
• Missing edge case handling: Failing to handle null inputs or properly initialize cloned nodes before processing neighbors

The most critical pitfall is assuming that node values are unique - this leads to incorrect cloning when multiple nodes share the same value but must be distinct objects in the cloned graph.

9. Alternative Approaches

There are several alternative approaches to solving the clone graph problem, each with different trade-offs:

Breadth-First Search (BFS) Approach: Instead of using DFS recursion, we can use an iterative BFS with a queue. This approach maintains the same time complexity O(V + E) but uses O(V) space for the queue and visited set. The main advantage is avoiding potential stack overflow issues with very deep graphs, though for most practical purposes this isn't a concern.

Two-Phase Approach with Node Mapping: We could first create all cloned nodes without any connections, then iterate through the original graph again to establish all the edges in the cloned graph. This requires two passes but might be more intuitive for some developers.

Iterative DFS with Stack: Similar to BFS, we can implement iterative DFS using an explicit stack instead of recursion. This approach is essentially the same as the recursive solution in terms of complexity but avoids potential recursion limits.

Hash Map with Lazy Cloning: Instead of cloning all nodes upfront, we could use a hash map that lazily creates clones only when needed. This approach can be slightly more memory-efficient in sparse graphs but adds complexity to the logic.

The chosen recursive DFS solution is preferred because it's clean, readable, and handles the graph traversal naturally. The recursive approach is more intuitive for graph problems and has minimal overhead compared to the iterative versions, which require additional data structures like explicit stacks or queues. The memory usage is also more predictable and the code is simpler to reason about.

The key advantage of the recursive approach here is that it naturally mirrors the structure of graph traversal, making the solution more maintainable and less error-prone than explicit stack-based implementations.

10. Test Cases

// Test case 1: Simple linear graph
// 1-2-3
@Test
public void testSimpleLinearGraph() {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    
    node1.neighbors.add(node2);
    node2.neighbors.add(node3);
    
    Node cloned = cloneGraph(node1);
    assertNotNull(cloned);
    assertEquals(1, cloned.val);
    assertEquals(1, cloned.neighbors.size());
    assertEquals(2, cloned.neighbors.get(0).val);
}

// Test case 2: Graph with cycle
// 1-2-3-4
// |____|
@Test
public void testGraphWithCycle() {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    
    node1.neighbors.add(node2);
    node2.neighbors.add(node3);
    node3.neighbors.add(node4);
    node4.neighbors.add(node1); // cycle
    
    Node cloned = cloneGraph(node1);
    assertNotNull(cloned);
    assertEquals(1, cloned.val);
}

// Test case 3: Empty graph
@Test
public void testEmptyGraph() {
    assertNull(cloneGraph(null));
}

// Test case 4: Single node
@Test
public void testSingleNode() {
    Node node = new Node(1);
    Node cloned = cloneGraph(node);
    assertNotNull(cloned);
    assertEquals(1, cloned.val);
    assertTrue(cloned.neighbors.isEmpty());
}

// Test case 5: Complex graph with multiple connections
@Test
public void testComplexGraph() {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    
    // 1 connects to 2 and 4
    // 2 connects to 1 and 3
    // 3 connects to 2 and 4
    // 4 connects to 1 and 3
    
    node1.neighbors.add(node2);
    node1.neighbors.add(node4);
    node2.neighbors.add(node1);
    node2.neighbors.add(node3);
    node3.neighbors.add(node2);
    node3.neighbors.add(node4);
    node4.neighbors.add(node1);
    node4.neighbors.add(node3);
    
    Node cloned = cloneGraph(node1);
    assertNotNull(cloned);
    assertEquals(1, cloned.val);
}

11. Final Summary

The core idea is to perform a deep copy of a connected undirected graph by traversing all nodes and their neighbors while maintaining a mapping between original and cloned nodes to avoid cycles. This solution works efficiently by using a single DFS traversal with a hash map to track already cloned nodes, ensuring each node is processed exactly once. The approach is optimal with O(V + E) time and space complexity where V is the number of nodes and E is the number of edges, making it ideal for graph cloning scenarios where node references must be preserved across the clone.