Crack the Backend

Problem Statement

Given a reference to a node in a connected undirected graph (each node has a val and a list of neighbors), return a deep copy (clone) of the graph. Every node and edge must be copied; the clone should have the same structure but new node instances. If the graph is empty (node is null), return null.

We need a mapping from original node → clone node. When we traverse, for each neighbor we either get the existing clone from the map or create a new clone and add it to the map and the traversal. We then add the clone of the neighbor to the current clone's neighbors list. BFS or DFS both work.

Key Observations

BFS: Map<Node, Node> map. Clone the start node, put in map, enqueue start. While queue not empty: dequeue cur, clone cloneCur = map.get(cur). For each neighbor of cur: if neighbor not in map, create clone, put in map, enqueue neighbor. Add map.get(neighbor) to cloneCur.neighbors. Return map.get(node).
We enqueue the original nodes and use the map to get or create clones; we never enqueue a clone.

Approach

High-level: map = original → clone. Clone start, map.put(start, cloneStart), queue.add(start). While queue not empty: cur = queue.poll(), cloneCur = map.get(cur); for each neighbor: if !map.containsKey(neighbor) create clone, map.put, queue.add(neighbor); cloneCur.neighbors.add(map.get(neighbor)). Return map.get(node).

Implementation

Java

public Node cloneGraph(Node node) {

    if (node == null) {
        return null;
    }

    Map<Node, Node> map = new HashMap<>();
    map.put(node, new Node(node.val));
    Queue<Node> q = new ArrayDeque<>();
    q.offer(node);

    while (!q.isEmpty()) {
        Node cur = q.poll();

        for (Node nb : cur.neighbors) {
            if (!map.containsKey(nb)) {
                map.put(nb, new Node(nb.val));
                q.offer(nb);
            }

            map.get(cur).neighbors.add(map.get(nb));
        }
    }

    return map.get(node);
}

Test Cases

Example 1

Input

adjList = [[2,4],[1,3],[2,4],[1,3]]

Expected

Deep copy

Explanation

Same structure, new nodes.

Complexity Analysis

Time: O(V+E).
Space: O(V).

Follow-ups

Clone list with random pointer.