Clone Graph

Medium Graphs BFS / DFS Basics Original on LeetCode

Clone Graph is a medium graphs problem solved with the bfs / dfs basics pattern. The best approach, optimal (bfs with a map from original to copy), runs in O(V + E) time and O(V) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from dfs with a map from original to copy up.

Problem

You are given a reference to one node of a connected, undirected graph. Each node stores an integer val and a list neighbors of the nodes it is connected to. Return a deep copy of the whole graph: a brand-new set of nodes with the same values and the same connections, where no node of the copy is a node of the original.

In the examples the graph is written as an adjacency list: entry i (1-based) lists the values of node i’s neighbors. The node you receive is always the one with value 1, and node i has value i. If the graph is empty, the given node is null and you return null.

Examples

Example 1

Input
adjList = [[2, 3], [1, 3], [1, 2]]
Output
[[2, 3], [1, 3], [1, 2]]
Why
A triangle: every node touches the other two. The copy has three new nodes wired the same way.

Example 2

Input
adjList = [[2], [1, 3], [2, 4], [3]]
Output
[[2], [1, 3], [2, 4], [3]]
Why
A path 1 - 2 - 3 - 4. Starting from node 1, every node is reached and copied.

Example 3

Input
adjList = []
Output
[]
Why
There is no graph, so the answer is null.

Constraints

  • 0 <= number of nodes <= 100
  • 1 <= Node.val <= 100, and every value is unique (node i has value i).
  • The graph is undirected and connected, with no self-loops and no repeated edges.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
DFS with a map from original to copyO(V + E)O(V)
Optimal (BFS with a map from original to copy)O(V + E)O(V)

1DFS with a map from original to copy

TimeO(V + E)Each node is copied once and each edge is followed twice (once from each end).
SpaceO(V)The map holds V entries and the recursion can go V levels deep.

Recursively copy the graph. Before copying a node, look it up in a map; if it is already there, return the existing copy, which also stops the recursion on cycles.

  1. If the node is null, return null.
  2. If the map already holds a copy of this node, return it.
  3. Create the copy, store it in the map before visiting neighbors.
  4. For each neighbor, append clone(neighbor) to the copy's neighbor list.
class Solution {
    private final Map<Node, Node> copies = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Node seen = copies.get(node);
        if (seen != null) return seen;
        Node copy = new Node(node.val);
        copies.put(node, copy);
        for (Node nb : node.neighbors) {
            copy.neighbors.add(cloneGraph(nb));
        }
        return copy;
    }
}

2Optimal (BFS with a map from original to copy)

TimeO(V + E)Every node is enqueued once and every adjacency entry is scanned once.
SpaceO(V)The map and the queue each hold at most V nodes.

Walk the graph level by level with a queue. The first time a node is seen, create its copy and enqueue it. When a node is dequeued, link its copy to the copies of all its neighbors. No recursion, so a long path cannot overflow the call stack.

  1. If the node is null, return null.
  2. Copy the start node, put it in the map and in the queue.
  3. Pop a node; for every neighbor: if it has no copy yet, create one, store it and enqueue the neighbor.
  4. Append the neighbor's copy to the popped node's copy.
  5. Return the copy of the start node.
class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> copies = new HashMap<>();
        copies.put(node, new Node(node.val));
        Deque<Node> queue = new ArrayDeque<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            for (Node nb : cur.neighbors) {
                if (!copies.containsKey(nb)) {
                    copies.put(nb, new Node(nb.val));
                    queue.add(nb);
                }
                copies.get(cur).neighbors.add(copies.get(nb));
            }
        }
        return copies.get(node);
    }
}

Edge cases to test

  • An empty graph (the given node is null)
  • A single node with no neighbors
  • Cycles: without remembering visited nodes the copy loops forever

Hints

Hint 1

Each original node must map to exactly one copy. What structure lets you ask "have I already copied this node?"

Hint 2

Keep a map from original node to its copy. Create the copy the first time you see a node, then fill its neighbor list with the copies of its neighbors.

Hint 3

Either DFS (recursion) or BFS (a queue) can drive the walk; the map doubles as the visited set.

FAQ

What is the best time complexity for Clone Graph?

Optimal (BFS with a map from original to copy) runs in O(V + E) time and O(V) extra space. Every node is enqueued once and every adjacency entry is scanned once.

Which pattern does Clone Graph use?

It is a graphs problem that uses the bfs / dfs basics pattern. Other problems with the same pattern: BFS - Normal + Level by Level, DFS - Recursive + Iterative, All Paths From Source to Target.

Is there a brute force solution for Clone Graph?

Yes. DFS with a map from original to copy takes O(V + E) time and O(V) space. Recursively copy the graph.

Which edge cases should I test for Clone Graph?

An empty graph (the given node is null); A single node with no neighbors; Cycles: without remembering visited nodes the copy loops forever.