81.Clone Graph

MediumBlind 75Graphs · 2/19

Problem

You are given a reference to one node of a connected, undirected graph. Return a deep copy (clone) of the whole graph.

Each node has an integer val and a list of neighbors. The clone must consist of brand-new Node objects with the same values and the same neighbour structure — no node in the copy may point to a node of the original graph.

For testing, node values are 1..n and the graph is given as an adjacency list where index i lists the neighbours of node i + 1. The given node is always node 1 (or null for an empty graph).

Examples

Input:  adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: 4 nodes in a square: 1-2, 2-3, 3-4, 4-1. The output has the same shape but every node is a new object.

Input:  adjList = [[]]
Output: [[]]
Explanation: A single node with no neighbours.

Input:  adjList = []
Output: []
Explanation: Empty graph — the input node is null.

Constraints

The number of nodes is in the range [0, 100]
1 <= Node.val <= 100, and every Node.val is unique
No repeated edges and no self-loops
The graph is connected, so every node is reachable from the given node

💡 Key Insight

The graph has cycles (an undirected edge 1-2 means 1 lists 2 and 2 lists 1), so naive recursion would loop forever. Keep a map original → clone. The map doubles as the visited set: before cloning a node, check if its copy already exists and reuse it. Registering the clone in the map before visiting its neighbours is what breaks cycles. With O(1) hash lookups, every node and edge is processed once.

Brute Force (Two Passes with List Lookup)

TimeO(V·(V + E))SpaceO(V)

Intuition

Split the job in two: first discover every node, then build copies and wire their edges. If we keep the originals in a List and the copies in a parallel List at the same indices, the copy of any original is copies.get(originals.indexOf(original)). That lookup is a linear scan, which is what makes this the slow version.

Algorithm

If node == null, return null.
BFS from node, appending each newly discovered node to originals (contains is used as the visited check).
Create copies.get(i) = new Node(originals.get(i).val) for every index.
For each original i and each neighbour nb, append copies.get(originals.indexOf(nb)) to copies.get(i).neighbors.
Return copies.get(0).

Visualization

originals = [n1, n2, n4, n3]     (BFS order from node 1)
copies    = [c1, c2, c4, c3]     (same indices)

wire n1.neighbors = [n2, n4] → indexOf = 1, 2 → c1.neighbors = [c2, c4]
wire n2.neighbors = [n1, n3] → indexOf = 0, 3 → c2.neighbors = [c1, c3]
...each indexOf is a linear scan of originals

Code

java

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

import java.util.*;

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;

        // Pass 1: discover every node (BFS); contains() is an O(V) scan
        List<Node> originals = new ArrayList<>();
        Deque<Node> queue = new ArrayDeque<>();
        originals.add(node);
        queue.offer(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            for (Node nb : cur.neighbors) {
                if (!originals.contains(nb)) {
                    originals.add(nb);
                    queue.offer(nb);
                }
            }
        }

        // Pass 2: one copy per original, at the same index
        List<Node> copies = new ArrayList<>();
        for (Node orig : originals) {
            copies.add(new Node(orig.val));
        }

        // Pass 3: wire edges by locating each neighbour's index
        for (int i = 0; i < originals.size(); i++) {
            for (Node nb : originals.get(i).neighbors) {
                copies.get(i).neighbors.add(copies.get(originals.indexOf(nb)));
            }
        }
        return copies.get(0);
    }
}

Complexity

Time: O(V·(V + E)) — every visited-check and every edge lookup is a linear contains / indexOf over V nodes.
Space: O(V) — the two lists and the BFS queue.

DFS with HashMap

TimeO(V + E)SpaceO(V)

Intuition

Replace the list scans with a HashMap<Node, Node> from original to clone. A recursive clone(node) returns the existing copy if the map already has one; otherwise it creates the copy, puts it in the map immediately, then recursively clones each neighbour and adds it to the copy's neighbour list. When the recursion comes back around a cycle, it finds the half-built copy in the map and simply links to it.

Algorithm

If node == null, return null.
If cloned contains node, return cloned.get(node).
Create copy = new Node(node.val) and store cloned.put(node, copy).
For each neighbour nb, append cloneGraph(nb) to copy.neighbors.
Return copy.

Dry Run

Square graph 1-2-3-4-1:

flowchart TD
    A["clone(1): create c1"] --> B["clone(2): create c2"]
    B --> C["clone(1): in map, return c1"]
    B --> D["clone(3): create c3"]
    D --> E["clone(2): in map, return c2"]
    D --> F["clone(4): create c4"]
    F --> G["clone(1): in map<br/>clone(3): in map"]
    A --> H["clone(4): in map, return c4"]

Code

java

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

import java.util.*;

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

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (cloned.containsKey(node)) {
            return cloned.get(node); // already copied (breaks cycles)
        }
        Node copy = new Node(node.val);
        cloned.put(node, copy); // register BEFORE recursing into neighbours
        for (Node nb : node.neighbors) {
            copy.neighbors.add(cloneGraph(nb));
        }
        return copy;
    }
}

Complexity

Time: O(V + E) — each node is created once and each adjacency entry is followed once.
Space: O(V) — the map plus a recursion stack up to depth V (a long path graph).

BFS with HashMapOptimal

TimeO(V + E)SpaceO(V)

Intuition

Same map, iterative traversal. Clone the start node and put it in the queue. When a node is popped, look at each neighbour: if it has no clone yet, create one, record it, and enqueue the original neighbour so its own edges get wired later. In every case append the neighbour's clone to the popped node's clone. No recursion means no stack-depth concerns.

Algorithm

If node == null, return null.
cloned.put(node, new Node(node.val)); enqueue node.
While the queue is non-empty, pop cur. For each nb in cur.neighbors:
- If nb is not in cloned, add cloned.put(nb, new Node(nb.val)) and enqueue nb.
- Append cloned.get(nb) to cloned.get(cur).neighbors.
Return cloned.get(node).

Dry Run

Square graph, adjacency 1:[2,4] 2:[1,3] 3:[2,4] 4:[1,3]:

flowchart TD
    S["map {1:c1}<br/>queue [1]"] --> P1["pop 1: clone 2, 4<br/>c1.nbrs = [c2, c4]<br/>queue [2, 4]"]
    P1 --> P2["pop 2: 1 known, clone 3<br/>c2.nbrs = [c1, c3]<br/>queue [4, 3]"]
    P2 --> P3["pop 4: 1, 3 known<br/>c4.nbrs = [c1, c3]<br/>queue [3]"]
    P3 --> P4["pop 3: 2, 4 known<br/>c3.nbrs = [c2, c4]<br/>queue []"]
    P4 --> R["return c1"]

Code

java

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

import java.util.*;

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;

        Map<Node, Node> cloned = new HashMap<>();
        Deque<Node> queue = new ArrayDeque<>();
        cloned.put(node, new Node(node.val));
        queue.offer(node);

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            for (Node nb : cur.neighbors) {
                if (!cloned.containsKey(nb)) {
                    cloned.put(nb, new Node(nb.val)); // first time seen: copy it
                    queue.offer(nb);                  // wire its edges later
                }
                cloned.get(cur).neighbors.add(cloned.get(nb));
            }
        }
        return cloned.get(node);
    }
}

Complexity

Time: O(V + E) — each node is enqueued once and each adjacency entry is processed once.
Space: O(V) — the map and the queue.

Complexity Comparison

Approach	Time	Space
Brute Force (List Lookup)	O(V·(V + E))	O(V)
DFS + HashMap	O(V + E)	O(V)
BFS + HashMap	O(V + E)	O(V)

Common Pitfalls

Putting the clone into the map after recursing into neighbours — the cycle 1 → 2 → 1 then recurses forever (StackOverflowError).
Returning the original node (or adding original neighbours to the clone) — the result must contain only new objects.
Forgetting the null input case for an empty graph.
Marking visited by val in a boolean[] but still creating a second Node for the same value — always reuse the stored clone.
In BFS, enqueuing a neighbour every time it is seen instead of only when its clone is first created, which duplicates edges in the copy.