Clone Graph

Medium Problem 101 of 151 Java and Python

Problem

Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Each node has a value val and a list of neighbors.

Node values are 1 to n and unique; the given node has value 1.

Example 1

Input: adjList = [[2, 4], [1, 3], [2, 4], [1, 3]]
Output: [[2, 4], [1, 3], [2, 4], [1, 3]]
Why: A square: 1–2–3–4–1, copied node for node.

Example 2

Input: adjList = [[]]
Output: [[]]
Why: One node, no edges.

Constraints

0 ≤ number of nodes ≤ 100
No repeated edges or self-loops.

Explanation

Graphs have cycles, so a naive recursive copy would loop forever. Keep a map from each original node to its copy. When you meet a node that is already in the map, reuse its copy instead of copying it again.

Approach 1 · Better

BFS with a map

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

Copy the start node, then BFS. For each neighbour, create its copy the first time you see it, and add the copied edge.

Map the start node to a new copy; put the start in a queue.
Pop a node; for each neighbour, if it is not in the map, copy it and enqueue it.
Append the neighbour's copy to the current node's copy.

Java

import java.util.*;

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 current = queue.poll();
            for (Node neighbor : current.neighbors) {
                if (!copies.containsKey(neighbor)) {
                    copies.put(neighbor, new Node(neighbor.val));
                    queue.add(neighbor);
                }
                copies.get(current).neighbors.add(copies.get(neighbor));
            }
        }
        return copies.get(node);
    }
}

Python

from collections import deque

class Solution:
    def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:
        if not node:
            return None
        copies = {node: Node(node.val)}
        queue = deque([node])
        while queue:
            current = queue.popleft()
            for neighbor in current.neighbors:
                if neighbor not in copies:
                    copies[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)
                copies[current].neighbors.append(copies[neighbor])
        return copies[node]

Approach 2 · Optimal

Recursive DFS with a map

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

To clone a node: if it is already cloned, return the clone; otherwise create the clone, store it before recursing, then clone each neighbour.

clone(node): return map[node] if present.
Create copy, store map[node] = copy.
For each neighbour, append clone(neighbour) to copy.neighbors.

Java

import java.util.*;

class Solution {
    private final Map<Node, Node> copies = new HashMap<>();

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

Python

class Solution:
    def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:
        copies = {}

        def clone(original):
            if original in copies:
                return copies[original]
            copy = Node(original.val)
            copies[original] = copy
            for neighbor in original.neighbors:
                copy.neighbors.append(clone(neighbor))
            return copy

        return clone(node) if node else None

Complexity compared

Approach	Time	Space
Better BFS with a map	O(V + E)	O(V)
Optimal Recursive DFS with a map	O(V + E)	O(V)

Key takeaways

Store the copy in the map before visiting neighbours; otherwise a cycle sends you back to an uncopied node forever.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem