Make an Independent Copy of a Connected Network

Medium25–30 min

Topics

GraphDFSBFSHash MapDeep Copy

Companies

AmazonFacebookGoogleMicrosoftBloomberg

You are given one node of a connected, undirected graph; every node has an integer value and a list of the nodes it is connected to. Return a deep copy of the graph: brand-new nodes with the same values and the same neighbours (in the same order), sharing no node with the original. For practice, graphs are written as adjacency lists (row i lists the values of the neighbours of node i + 1).

A graph can contain cycles, so simply following neighbours would never end. Remember which originals already have a copy — a dictionary from original to copy — so every node is copied exactly once.

Test Case 1:

Input:graph = [[2,3],[1,4],[1,4],[2,3,5],[4]]

Output:[[2,3],[1,4],[1,4],[2,3,5],[4]]

Explanation:Adjacency matrix (rows 1–5): 1: 0 1 1 0 0 · 2: 1 0 0 1 0 · 3: 1 0 0 1 0 · 4: 0 1 1 0 1 · 5: 0 0 0 1 0. A square 1–2–4–3 with a tail 4–5. The copy has the same lists, but every node in it is new.

Test Case 2:

Input:graph = [[]]

Output:[[]]

Explanation:A single node with no neighbours is copied into another single node.

Test Case 3:

Input:graph = []

Output:[]

Explanation:The empty graph (null) copies to null.

Constraints

◆0 ≤ number of nodes ≤ 100. The graph is undirected and CONNECTED; node values are 1, 2, …, n. You receive the node with value 1 (or null for an empty graph); each node has an integer val and a list neighbors of the nodes it is connected to
◆For testing, a graph is described by an adjacency list: row i (0-based) lists the values of the neighbours of the node with value i + 1, in the order they appear in that node's neighbors list. Example: [[2,3],[1],[1]] is a path 2 – 1 – 3
◆Return a deep copy: a graph of brand-new nodes with the same values and, at every node, the same neighbours in the same order. The copy may not share any node object with the original graph
◆The returned graph is printed as its adjacency list; a copy that reuses an original node is rejected

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Collect Every Node, Create All Copies, Then Wire Them Up

Good

Work in three passes. First, a breadth-first search from the given node collects every node of the graph in a list (a "seen" set prevents visiting a node twice). Second, create one brand-new node for every original node and remember the pairing original → copy in a dictionary. Third, walk the original nodes again and, for each original neighbour, append the neighbour's COPY to the copy's neighbour list, in the same order. Every node and every edge is processed a constant number of times: O(n + m) time and O(n) memory.

TimeO(n + m)

SpaceO(n)

Java

Try it out

class Solution {
    public GraphNode cloneGraph(GraphNode node) {
        if (node == null) return null;
        List<GraphNode> order = new ArrayList<>();
        Set<GraphNode> seen = new HashSet<>();
        Deque<GraphNode> queue = new ArrayDeque<>();
        queue.add(node);
        seen.add(node);
        while (!queue.isEmpty()) {
            GraphNode cur = queue.poll();
            order.add(cur);
            for (GraphNode next : cur.neighbors) {
                if (seen.add(next)) queue.add(next);
            }
        }
        Map<GraphNode, GraphNode> copy = new HashMap<>();
        for (GraphNode original : order) copy.put(original, new GraphNode(original.val));
        for (GraphNode original : order) {
            for (GraphNode next : original.neighbors) {
                copy.get(original).neighbors.add(copy.get(next));
            }
        }
        return copy.get(node);
    }
}

Optimal — One Depth-First Pass With a Map From Original to Copy

Optimal

Do it all in one recursive walk. Keep a dictionary from original node to its copy. To clone a node: if it is already in the dictionary, return that copy (this is what stops the endless walking around cycles and keeps shared neighbours shared); otherwise create the copy, record it in the dictionary BEFORE recursing, then clone each neighbour in order and append the results to the copy's list. Recording the copy first is essential — a neighbour that leads back to this node will then find it. O(n + m) time, O(n) memory.