Clone a graph

The problem, simply

You get one node of a connected undirected graph. Each node has a number val and a list neighbors of the nodes it is joined to.

Give back a deep copy: brand new nodes with the same numbers and the same joins. No new node may point to an old node.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do it in two passes, like making all the dolls first and the bracelets second.

1. Walk the whole graph from the given node with a waiting line. For every node you meet for the first time, make its copy and write "old to new" in a map.
2. Go through the map. For each old node, look at its neighbors and add each neighbor's copy, found in the map, to the new node's list.
3. Return the copy of the given node.

class CloneTwoPasses {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> copyOf = new HashMap<>();
        Queue<Node> line = new ArrayDeque<>();
        copyOf.put(node, new Node(node.val));
        line.add(node);
        while (!line.isEmpty()) {                    // pass 1: make every doll
            Node cur = line.poll();
            for (Node nb : cur.neighbors) {
                if (!copyOf.containsKey(nb)) {
                    copyOf.put(nb, new Node(nb.val));
                    line.add(nb);
                }
            }
        }
        for (Map.Entry<Node, Node> e : copyOf.entrySet()) {   // pass 2: make every bracelet
            for (Node nb : e.getKey().neighbors) {
                e.getValue().neighbors.add(copyOf.get(nb));
            }
        }
        return copyOf.get(node);
    }
}

How long it takes: each node and each join is handled a constant number of times, O(V + E). Extra room: the map and the line, O(V). It is correct, but it walks over the graph twice.

Way 2: the clever way

Do both jobs in one trip. When you stand on a node and look at a neighbor, you need that neighbor's copy right now. If the notebook has it, use it. If not, make it, write it down, and put the old neighbor in the line so its own neighbors get handled later.

1. Copy the given node, write it in the map, and put it in the line.
2. Take a node cur from the front. For each neighbor nb:
3. If nb has no copy, make one, store it, and add nb to the line.
4. Add the copy of nb to the neighbor list of the copy of cur.

class CloneBfs {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> copyOf = new HashMap<>();    // the notebook: old node to new node
        Queue<Node> line = new ArrayDeque<>();
        copyOf.put(node, new Node(node.val));
        line.add(node);
        while (!line.isEmpty()) {
            Node cur = line.poll();
            for (Node nb : cur.neighbors) {
                if (!copyOf.containsKey(nb)) {       // first time we see nb
                    copyOf.put(nb, new Node(nb.val));
                    line.add(nb);
                }
                copyOf.get(cur).neighbors.add(copyOf.get(nb));  // copy points to copy
            }
        }
        return copyOf.get(node);
    }
}

How long it takes: every node enters the line once and every neighbor entry is read once, O(V + E). Extra room: the map holds V pairs and the line up to V nodes, O(V).

Another way: recursion

Depth first is even shorter. To copy a node: if it is in the notebook, return its copy. Otherwise make the copy, write it down first, and then copy each neighbor by calling yourself.

class CloneDfs {
    private final Map<Node, Node> copyOf = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (copyOf.containsKey(node)) return copyOf.get(node);
        Node copy = new Node(node.val);
        copyOf.put(node, copy);                      // write it down before going deeper
        for (Node nb : node.neighbors) {
            copy.neighbors.add(cloneGraph(nb));
        }
        return copy;
    }
}

Writing the copy into the map before visiting neighbors is what stops the loop 1, 2, 1, 2, and so on. The recursion can be V calls deep, so a long chain can overflow the call stack.

Watch out for

• Keying the map by val works only if values are unique. Keying by the node object always works.
• A static map that is never cleared leaks copies between test cases. Keep it as a field of the object or a local variable.
• Adding the old neighbor (nb) instead of its copy (copyOf.get(nb)) makes a copy that secretly points back into the original.
• The empty graph: return null before touching anything.

What interviewers ask next

• Copy a linked list with random pointers: the same notebook idea, or the trick of weaving copies between originals for O(1) extra room.
• What if the graph is not connected and you get a list of all nodes? Run the same loop from every node that is not yet in the map.
• Directed graphs? The code is identical. It copies whatever the neighbors lists say.
• How do you test that it is a real deep copy? Walk both graphs together and check that no new node is == to an old one, while values and list orders match.

Remember this

Grown-up words: kids are nodes, bracelets are neighbor lists, the dolls are the deep copy, the notebook is a hash map from original to clone, the waiting line is a queue for breadth first search, and the recursive version is depth first search.