Clone Graph

medium
GraphsGraphDepth-First SearchBreadth-First SearchHash Table

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value val and a list of its neighbors neighbors.

Each node's value is the same as the node's index (1-indexed). For example, the first node has val == 1, the second node has val == 2, and so on. The graph is represented in the test case using an adjacency list where adjList[i] is a list of nodes adjacent to node i.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Examples

Example 1

  • Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
  • Output: [[2,4],[1,3],[2,4],[1,3]]
  • Explanation: There are 4 nodes in the graph. Node 1 connects to nodes 2 and 4. Node 2 connects to nodes 1 and 3. Node 3 connects to nodes 2 and 4. Node 4 connects to nodes 1 and 3. The cloned graph has the same structure.

Example 2

  • Input: adjList = [[]]
  • Output: [[]]
  • Explanation: The graph contains a single node with no neighbors.

Example 3

  • Input: adjList = []
  • Output: []
  • Explanation: The graph is empty (null node), so return null.

Constraints

  • The number of nodes in the graph is in the range [0, 100].
  • 1 <= Node.val <= 100
  • Node.val is unique for each node.
  • There are no repeated edges and no self-loops in the graph.
  • The graph is connected and all nodes can be visited starting from the given node.

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

DFS with Hash Map

Intuition

We can clone the graph using depth-first search while maintaining a hash map from original nodes to their clones. When we visit a node, we create its clone and store it in the map. Then we recursively clone all neighbors. If a neighbor has already been cloned (exists in the map), we reuse the existing clone instead of creating a new one. This prevents infinite loops caused by cycles in the graph and ensures each node is cloned exactly once.

Algorithm

  1. If the input node is null, return null.
  2. Create a hash map to store the mapping from original nodes to cloned nodes.
  3. Start DFS from the given node. Create a clone of the current node and add it to the map.
  4. For each neighbor of the current node, check if it already exists in the map.
  5. If the neighbor is already cloned, add the existing clone to the current clone's neighbor list.
  6. If not, recursively clone the neighbor and add the result to the current clone's neighbor list.
  7. Return the clone of the starting node.
TimeO(V + E) where V is the number of nodes and E is the number of edgesSpaceO(V) for the hash map and recursion stack

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    unordered_map<Node*, Node*> visited;

    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;

        if (visited.count(node)) {
            return visited[node];
        }

        Node* clone = new Node(node->val);
        visited[node] = clone;

        for (Node* neighbor : node->neighbors) {
            clone->neighbors.push_back(cloneGraph(neighbor));
        }

        return clone;
    }
};
Java 21
class Solution {
    private Map<Node, Node> visited = new HashMap<>();

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

        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        Node clone = new Node(node.val);
        visited.put(node, clone);

        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }

        return clone;
    }
}
Python 3.12
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None

        visited = {}

        def dfs(node):
            if node in visited:
                return visited[node]

            clone = Node(node.val)
            visited[node] = clone

            for neighbor in node.neighbors:
                clone.neighbors.append(dfs(neighbor))

            return clone

        return dfs(node)
Go 1.26
func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }

    visited := make(map[*Node]*Node)

    var dfs func(*Node) *Node
    dfs = func(n *Node) *Node {
        if clone, ok := visited[n]; ok {
            return clone
        }

        clone := &Node{Val: n.Val}
        visited[n] = clone

        for _, neighbor := range n.Neighbors {
            clone.Neighbors = append(clone.Neighbors, dfs(neighbor))
        }

        return clone
    }

    return dfs(node)
}
Approach 2

BFS with Hash Map

Intuition

Instead of DFS, we can use breadth-first search to traverse the graph level by level. We start by cloning the root node and adding it to a queue. For each node dequeued, we iterate through its neighbors. If a neighbor hasn't been cloned yet, we create its clone, store it in the map, and enqueue it. We then connect the current clone to the neighbor's clone. BFS ensures we process all nodes at the current depth before moving deeper.

Algorithm

  1. If the input node is null, return null.
  2. Create a hash map and clone the starting node, adding the mapping to the map.
  3. Initialize a queue with the original starting node.
  4. While the queue is not empty, dequeue a node.
  5. For each neighbor of the dequeued node, if it hasn't been cloned, create a clone and enqueue the original neighbor.
  6. Add the neighbor's clone to the current node's clone's neighbor list.
  7. Return the clone of the starting node from the map.
TimeO(V + E) where V is the number of nodes and E is the number of edgesSpaceO(V) for the hash map and queue

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;

        unordered_map<Node*, Node*> visited;
        visited[node] = new Node(node->val);

        queue<Node*> q;
        q.push(node);

        while (!q.empty()) {
            Node* curr = q.front();
            q.pop();

            for (Node* neighbor : curr->neighbors) {
                if (!visited.count(neighbor)) {
                    visited[neighbor] = new Node(neighbor->val);
                    q.push(neighbor);
                }
                visited[curr]->neighbors.push_back(visited[neighbor]);
            }
        }

        return visited[node];
    }
};
Java 21
class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;

        Map<Node, Node> visited = new HashMap<>();
        visited.put(node, new Node(node.val));

        Queue<Node> queue = new LinkedList<>();
        queue.add(node);

        while (!queue.isEmpty()) {
            Node curr = queue.poll();

            for (Node neighbor : curr.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    visited.put(neighbor, new Node(neighbor.val));
                    queue.add(neighbor);
                }
                visited.get(curr).neighbors.add(visited.get(neighbor));
            }
        }

        return visited.get(node);
    }
}
Python 3.12
from collections import deque


class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None

        visited = {node: Node(node.val)}
        queue = deque([node])

        while queue:
            curr = queue.popleft()

            for neighbor in curr.neighbors:
                if neighbor not in visited:
                    visited[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)
                visited[curr].neighbors.append(visited[neighbor])

        return visited[node]
Go 1.26
func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }

    visited := make(map[*Node]*Node)
    visited[node] = &Node{Val: node.Val}

    queue := []*Node{node}

    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]

        for _, neighbor := range curr.Neighbors {
            if _, ok := visited[neighbor]; !ok {
                visited[neighbor] = &Node{Val: neighbor.Val}
                queue = append(queue, neighbor)
            }
            visited[curr].Neighbors = append(visited[curr].Neighbors, visited[neighbor])
        }
    }

    return visited[node]
}

Frequently asked questions

What is the optimal time complexity of Clone Graph?

The most efficient approach in this guide ("BFS with Hash Map") runs in O(V + E) where V is the number of nodes and E is the number of edges time and uses O(V) for the hash map and queue extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Clone Graph use?

Clone Graph is a medium-level Graphs problem involving Graph, Depth-First Search, Breadth-First Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Clone Graph be solved without extra space?

The most space-efficient approach in this guide uses O(V) for the hash map and queue extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(V) for the hash map and recursion stack, while the optimized version uses O(V) for the hash map and queue.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
node=
[[2,4],[1,3],[2,4],[1,3]]
Expected Output
[[2,4],[1,3],[2,4],[1,3]]