medium Clone Graph

Problem Statement

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.

Example 1:

Input:

    1--2
    |  |
    4--3

Expected Output:

    1--2
    |  |
    4--3

Explanation: The graph has four nodes with the following connections:

• Node 1 is connected to nodes 2 and 4.
• Node 2 is connected to nodes 1 and 3.
• Node 3 is connected to nodes 2 and 4.
• Node 4 is connected to nodes 1 and 3.

Example 2:

Input:

    1--2
   /    \
  5      3
         |
         4

Expected Output:

    1--2
   /    \
  5      3
         |
         4

Explanation: The graph consists of five nodes with these connections:

• Node 1 is connected to nodes 2 and 5.
• Node 2 is connected to nodes 1 and 3.
• Node 3 is connected to nodes 2 and 4.
• Node 4 is connected to node 3.
• Node 5 is connected to node 1.

Example 3:

Input:

    1--2
   /    \
  4      3
   \    /
    5--6

Expected Output:

    1--2
   /    \
  4      3
   \    /
    5--6

Explanation: The graph has six nodes with the following connections:

• Node 1 is connected to nodes 2 and 4.
• Node 2 is connected to nodes 1 and 3.
• Node 3 is connected to nodes 2 and 6.
• Node 4 is connected to nodes 1 and 5.
• Node 5 is connected to nodes 4 and 6.
• Node 6 is connected to nodes 3 and 5.

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

To deep clone a given graph, the primary approach is to traverse the graph using Depth-First Search (DFS) and simultaneously create clones of the visited nodes. A hashmap (or dictionary) is utilized to track and associate original nodes with their respective clones, ensuring no duplications.

1. Initialization: Create an empty hashmap to match the original nodes to their clones.

2. DFS Traversal and Cloning: Traverse the graph with DFS. When encountering a node not in the hashmap, create its clone and map them in the hashmap. Recursively apply DFS for each of the node's neighbors. After cloning a node and all its neighbors, associate the cloned node with the clones of its neighbors.

3. Termination: Once DFS covers all nodes, return the cloned version of the starting node.

Algorithm Walkthrough (using Example 1):

For the input graph:

    1--2
    |  |
    4--3

• Start with an empty hashmap visited.
• Begin DFS with node 1.
  • Node 1 isn't in visited. Clone it to get 1' and map (1, 1') in the hashmap.
  • For each neighbor of node 1, apply DFS.
    • First with 2.
      • Node 2 isn't in visited. Clone to get 2' and map (2, 2').
      • Node 2's neighbors are 1 and 3. Node 1 is visited, so link 2' to 1'. Move to 3.
        • Node 3 isn't in visited. Clone to get 3' and map (3, 3').
        • Node 3 has neighbors 2 and 4. Node 2 is visited, so link 3' to 2'. Move to 4.
          • Node 4 isn't in visited. Clone to get 4' and map (4, 4').
          • Node 4 has neighbors 1 and 3, both visited. Link 4' to 1' and 3'.
• With DFS complete, return the clone of the starting node, 1'.

Code

import java.util.*;

//    public static class GraphNode {
//         public int val;
//         public List<GraphNode> neighbors;

//         public GraphNode() {
//             val = 0;
//             neighbors = new ArrayList<GraphNode>();
//         }

//         public GraphNode(int _val) {
//             val = _val;
//             neighbors = new ArrayList<GraphNode>();
//         }

//         public GraphNode(int _val, ArrayList<GraphNode> _neighbors) {
//             val = _val;
//             neighbors = _neighbors;
//         }
//     }

class Solution {

  // HashMap to store already visited nodes and their clones
  private Map<GraphNode, GraphNode> visited = new HashMap<>();

  public GraphNode cloneGraph(GraphNode node) {
    // Base condition if node is null
    if (node == null) return null;

    // Return the clone from the map if it's already visited
    if (visited.containsKey(node)) return visited.get(node);

    // Create a new node for the given value
    GraphNode cloneNode = new GraphNode(node.val, new ArrayList<>());
    visited.put(node, cloneNode);

    // Process all the neighbors for the node
    for (GraphNode neighbor : node.neighbors) {
      cloneNode.neighbors.add(cloneGraph(neighbor));
    }

    return cloneNode;
  }

  // Utility function to print the structure of the graph
  public static void printGraph(GraphNode node) {
    Set<GraphNode> printed = new HashSet<>();
    Queue<GraphNode> queue = new LinkedList<>();
    queue.add(node);

    while (!queue.isEmpty()) {
      GraphNode curr = queue.poll();
      if (!printed.contains(curr)) {
        System.out.print(curr.val + "-->");
        for (GraphNode n : curr.neighbors) {
          queue.add(n);
          System.out.print(n.val + " ");
        }
        System.out.println();
        printed.add(curr);
      }
    }
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    // Example 1: Create a simple two-node graph and clone it
    GraphNode node1 = new GraphNode(1);
    GraphNode node2 = new GraphNode(2);
    node1.neighbors = Arrays.asList(node2);
    node2.neighbors = Arrays.asList(node1);
    printGraph(sol.cloneGraph(node1)); // Expecting: 1-->2, 2-->1
  }
}

Complexity Analysis

• Time Complexity: where N is the number of nodes and M is the number of edges. Each node and edge is visited once.

• Space Complexity: as we are creating a clone for each node. Additionally, the recursion stack might use where H is the depth of the graph (in the worst case this would be .

🎯 STRICT STANDOUT — Solution Clone Graph

0. Pattern family

Family: Graph clone BFS/DFS + hashmap

1. Why / judgment (K3)

Implement deep clone: if node is None return None. map = {}; BFS queue start with node; map[node]=Node(node.val); while queue: for each neighbor, if not in map create and enqueue; map[cur].neighbors.append(map[nei]). Critical: allocate clone before processing neighbors so cycles resolve. Object identity of clones must differ from originals (interview may check is not).

2. Worked complexity / derivation (K11)

V nodes, E undirected edges (each stored twice in adj lists).
Each node enqueued once; each adj entry scanned once → Θ(V+E) time.
Hash map Θ(V); queue O(V). DFS recursive O(V) stack risk on deep graphs — iterative safer for large V.

3. Pattern + recognition + when-NOT (K12)

Name: CLONE GRAPH MAP+TRAVERSAL

Recognition: connected undirected graph clone; cycles; return clone of given entry node.

When-NOT: If forest / disconnected, API only gives one node — only clone reachable component (problem usually connected). Copy list random pointer is same map pattern on linear nodes. Serialize to string and parse is alternative when map-by-identity unavailable across process.

4. Edge hand-run (K13)

null → null.
Single node neighbors=[] → new node same val empty list.
Two nodes 1—2: clones c1,c2; c1.neighbors=[c2], c2.neighbors=[c1]; c1 is not node1.
Cycle 1-2-3-4-1: after full BFS map has 4 entries; each neighbor list length matches original.
Self-loop if ever: map[node].neighbors.append(map[node]).

5. Interviewer follow-ups & drills

Q1. First step on visit?
Model answer: Create clone and put in map immediately, then wire neighbors.

Q2. Val collision?
Model answer: Prefer map keyed by original node reference; vals may theoretically collide.

Q3. How to test clone?
Model answer: Structure equal, no shared node objects; mutate clone neighbors doesn't affect original.

Q4. DFS recursion on clone?
Model answer: def clone(n): if n in map: return map[n]; map[n]=Node(n.val); then append clone(nei) — same map.