Clone Graph

To solve the Clone Graph problem efficiently, I would first clarify that we are dealing with an undirected graph which inherently contains cycles. My approach uses a Hash Map to map every original node to its corresponding clone, ensuring we never process the same node twice. I prefer using Breadth-First Search (BFS) here because it naturally handles level-by-level copying and avoids potential stack overflow issues that could occur with deep recursive DFS on large Salesforce-scale datasets. I will initialize a queue and a map. First, I check if the input node is null; if so, return null immediately. Otherwise, I create a clone of the starting node, store it in the map, and push the original into the queue. While the queue is not empty, I dequeue a current node. For each neighbor of this current node, I check if it exists in our map. If it does, I simply append that existing clone to the current clone's neighbor list. If it doesn't exist, I create a fresh clone, add it to the map, enqueue the original neighbor, and append the new clone to the current clone's list. This ensures every node is copied exactly once and all connections are preserved correctly, even across cycles. Finally, I return the clone of the initial node stored in the map.