Problem 23.9 · Depth-First SearchMedium

Clone Graph

PatternGraph DFS and Flood Fill Graph BFS Hash Map Lookup (Complement)

What it teaches: Copying a structure with cycles: a map from each original node to its copy doubles as the visited set.

Practise it on judges as “Clone Graph”.

In plain words

Imagine copying a group of friends and their friendships onto a new sheet of paper. For every person you draw a new circle, and for every friendship a new line between the new circles. The new drawing must not point back at the old one, and because friendships go both ways, you'll meet the same person many times: you must remember who you've already drawn.

Each Node has a value and a list of neighbours. Given one node of a connected undirected graph, return its copy: brand-new nodes with the same values and the same connections.

The problem

Return a deep copy of the connected undirected graph containing node. Each node has val (1..n, unique) and neighbors. Tests describe the graph as an adjacency list where entry i lists the neighbours of node i + 1, and check that your copy uses no original node objects.

Example 1

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]

Four nodes in a square: 1–2, 2–3, 3–4, 4–1.

Constraints

0 ≤ n ≤ 100
Connected, no repeated edges or self-loops

Pattern clues in the wording

→ Copy a structure that can contain cycles
→ Each object reachable many times

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

/*
class Node {
    public int val;
    public List<Node> neighbors;
}
*/
class Solution {
    public Node cloneGraph(Node node) {
        return null;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	node = [[2,4],[1,3],[2,4],[1,3]]	[[2,4],[1,3],[2,4],[1,3]]
2	node = [[]]	[[]]
3	node = []	[]

From slow to fast

Approaches

1. DFS with an original → copy map · O(V + E)2. BFS with the same map · O(V + E)

DFS with an original → copy map

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

clone(n): if n is in the map return its copy; otherwise create the copy, store it in the map before visiting neighbours (this stops cycles), then add clone(neighbour) for each neighbour.

▶ Dry run: Cloning the square 1–2–3–4adjList = [[2,4],[1,3],[2,4],[1,3]]

map (original → copy)(map)

1 → 1'

Step 1/3Copy node 1 and store it in the map before looking at its neighbours.

Approach 1

import java.util.*;

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);                  // store before recursing: stops cycles
        for (Node nb : node.neighbors) copy.neighbors.add(cloneGraph(nb));
        return copy;
    }
}

Verdict: The map is both the visited set and the lookup for copies.

BFS with the same map

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

Queue the start node with its copy; for each neighbour, create a copy the first time you meet it, enqueue it, and link copies.

Approach 2

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> q = new ArrayDeque<>();
        q.offer(node);
        while (!q.isEmpty()) {
            Node n = q.poll();
            for (Node nb : n.neighbors) {
                if (!copies.containsKey(nb)) {
                    copies.put(nb, new Node(nb.val));
                    q.offer(nb);
                }
                copies.get(n).neighbors.add(copies.get(nb));
            }
        }
        return copies.get(node);
    }
}

Verdict: No recursion depth limit.

Before you submit

Edge cases and common mistakes

Test these inputs

Empty graph (null)
A single node with no neighbours
Cycles

Mistakes people make

Adding the node to the map only after copying its neighbours (infinite recursion on cycles).
Returning original nodes inside the copy (a shallow copy).

Interview

Follow-up questions

How would you copy a linked list where each node also has a random pointer?

Command Palette