Clone Graph

Med

#0133Time: O(N + E), where N is the number of nodes and E is the number of edges. Each node is visited once, and we iterate through all its edges.Space: O(N), for the hash map which stores all N nodes, and for the recursion stack which can go up to N deep in the worst case (for a skewed graph).11 companies

Algorithms

Depth-First Search Breadth-First Search

Data structures

Hash Table Graph

Companies

Docusign Google Nutanix TikTok

Prompt

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 (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

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.

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.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.

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 approaches with complexity analysis and trade-offs.

This approach uses a recursive Depth-First Search (DFS) traversal to clone the graph. A hash map is used to store the mapping between original nodes and their newly created clones. This map is crucial to handle cycles and prevent re-cloning the same node multiple times.

Algorithm

1. Create a hash map visited to store the mapping from original nodes to their clones.
1. Define a recursive function clone(node):
a. If node is null, return null.
b. If visited contains node, return visited.get(node).
c. Create a new node cloneNode with node.val.
d. Add the mapping (node, cloneNode) to visited.
e. For each neighbor in node.neighbors:
i. Add the result of `clone(neighbor)` to `cloneNode.neighbors`.
f. Return cloneNode.
1. The main function cloneGraph simply calls clone(node).

Walkthrough

We start traversing the graph from the given node. We use a hash map, say visited, to keep track of nodes that have already been cloned. The map stores the original node as the key and its clone as the value. The core of the approach is a recursive function.

In the recursive function, for a given node:

If the node is already in our visited map, it means we have already created a copy for it. We simply return the copy from the map.
If the node is not in the map, we create a new Node with the same value.
We immediately put this new node into the visited map, with the original node as the key. This is important to do before traversing its neighbors to handle cycles correctly.
Then, we iterate through each neighbor of the original node.
For each neighbor, we make a recursive call. This call will return the cloned neighbor node (either by creating it or fetching it from the map).
We add this returned cloned neighbor to the neighbors list of our newly created node.
Finally, we return the new node.

The initial call to cloneGraph will just call this recursive helper function starting with the given node.

1/*2// Definition for a Node.3class Node {4    public int val;5    public List<Node> neighbors;6    public Node() {7        val = 0;8        neighbors = new ArrayList<Node>();9    }10    public Node(int _val) {11        val = _val;12        neighbors = new ArrayList<Node>();13    }14    public Node(int _val, ArrayList<Node> _neighbors) {15        val = _val;16        neighbors = _neighbors;17    }18}19*/20 21class Solution {22    private HashMap<Node, Node> visited = new HashMap<>();23 24    public Node cloneGraph(Node node) {25        if (node == null) {26            return node;27        }28 29        // If the node was already visited, return the clone from the map.30        if (visited.containsKey(node)) {31            return visited.get(node);32        }33 34        // Create a new node with the same value as the old node.35        Node cloneNode = new Node(node.val, new ArrayList<>());36        // Add the new node to the visited map.37        // This must be done before visiting the neighbors to prevent infinite loops.38        visited.put(node, cloneNode);39 40        // Iterate through the neighbors of the original node and recursively clone them.41        for (Node neighbor : node.neighbors) {42            cloneNode.neighbors.add(cloneGraph(neighbor));43        }44        return cloneNode;45    }46}

Complexity

Time

O(N + E), where N is the number of nodes and E is the number of edges. Each node is visited once, and we iterate through all its edges.

Space

O(N), for the hash map which stores all N nodes, and for the recursion stack which can go up to N deep in the worst case (for a skewed graph).

Trade-offs

Pros

Conceptually simple and often leads to more concise code.
Efficient, as it visits each node and edge only once.

Cons

For very deep graphs, the recursion could lead to a stack overflow error. (Though not an issue with the given constraints).

This approach uses an iterative Breadth-First Search (BFS) traversal. It uses a queue to manage the nodes to visit and a hash map to store the mapping from original nodes to their clones, just like the DFS approach. This avoids recursion and the potential for stack overflow.

Algorithm

1. If the input node is null, return null.
1. Create a Queue for BFS and add the starting node.
1. Create a HashMap<Node, Node> called visited to map original nodes to their clones.
1. Create the clone for the starting node, and put the mapping in visited.
1. While the queue is not empty:
a. Dequeue a node, originalNode.
b. For each neighbor of originalNode:
i. If `neighbor` is not in `visited`:
- Create a clone for `neighbor` and add it to `visited`.
- Enqueue the `neighbor`.

1ii. Add the cloned neighbor (`visited.get(neighbor)`) to the neighbor list of the cloned `originalNode` (`visited.get(originalNode).neighbors`).

1. Return the clone of the starting node from the visited map.

Walkthrough

The core idea is to create a copy of a node, then add its neighbors to a queue to be processed later. We use a hash map to ensure we don't create duplicate clones for the same node.

The algorithm proceeds as follows:

Handle the edge case where the input node is null.
Create a queue and add the starting node to it.
Create a hash map visited to store original_node -> cloned_node mappings.
Create the clone for the starting node and put it in the visited map.
While the queue is not empty: a. Dequeue a node, let's call it originalNode. b. Iterate through all neighbors of originalNode. c. For each neighbor: i. If the neighbor is not in the visited map, it means we haven't seen it before. So, we create a clone for it, add it to the visited map, and enqueue the original neighbor for later processing. d. After checking all neighbors, we connect the cloned originalNode to its cloned neighbors. We retrieve the clone of originalNode from the map and add the clones of its neighbors (also retrieved from the map) to its neighbor list.

1/*2// Definition for a Node.3class Node {4    public int val;5    public List<Node> neighbors;6    public Node() {7        val = 0;8        neighbors = new ArrayList<Node>();9    }10    public Node(int _val) {11        val = _val;12        neighbors = new ArrayList<Node>();13    }14    public Node(int _val, ArrayList<Node> _neighbors) {15        val = _val;16        neighbors = _neighbors;17    }18}19*/20 21class Solution {22    public Node cloneGraph(Node node) {23        if (node == null) {24            return null;25        }26 27        HashMap<Node, Node> visited = new HashMap<>();28        Queue<Node> queue = new LinkedList<>();29 30        // Clone the root node and add it to the queue and visited map.31        visited.put(node, new Node(node.val, new ArrayList<>()));32        queue.add(node);33 34        // Start BFS traversal35        while (!queue.isEmpty()) {36            // Get the original node from the front of the queue.37            Node originalNode = queue.poll();38 39            // Iterate through the neighbors of the original node.40            for (Node neighbor : originalNode.neighbors) {41                // If the neighbor hasn't been cloned yet.42                if (!visited.containsKey(neighbor)) {43                    // Clone it and add to the map.44                    visited.put(neighbor, new Node(neighbor.val, new ArrayList<>()));45                    // Add the original neighbor to the queue for processing.46                    queue.add(neighbor);47                }48                // Add the cloned neighbor to the neighbors list of the cloned current node.49                visited.get(originalNode).neighbors.add(visited.get(neighbor));50            }51        }52 53        return visited.get(node);54    }55}

Complexity

Time

O(N + E), where N is the number of nodes and E is the number of edges. Each node is enqueued and dequeued once, and we iterate through all its edges.

Space

O(N), for the hash map and the queue. The queue can hold up to O(W) nodes where W is the maximum width of the graph, which can be O(N) in the worst case.

Trade-offs

Pros

Iterative approach avoids recursion, preventing potential stack overflow errors on very large or deep graphs.
Efficient, as it visits each node and edge only once.

Cons

The code can be slightly more verbose than the recursive DFS version.

Solutions

Solution

1/** * // Definition for a _Node. * function _Node(val, neighbors) { * this.val = val === undefined ? 0 : val; * this.neighbors = neighbors === undefined ? [] : neighbors; * }; */ /** * @param {_Node} node * @return {_Node} */ var cloneGraph =2  function (node) {3    const g = new Map();4    const dfs = (node) => {5      if (!node) {6        return null;7      }8      if (g.has(node)) {9        return g.get(node);10      }11      const cloned = new _Node(node.val);12      g.set(node, cloned);13      for (const nxt of node.neighbors) {14        cloned.neighbors.push(dfs(nxt));15      }16      return cloned;17    };18    return dfs(node);19  };

1using System.Collections.Generic ; public class Solution { public Node CloneGraph ( Node node ) { if ( node == null ) return null ; var dict = new Dictionary < int , Node >(); var queue = new Queue < Node >(); queue . Enqueue ( CloneVal ( node )); dict . Add ( node . val , queue . Peek ()); while ( queue . Count > 0 ) { var current = queue . Dequeue (); var newNeighbors = new List < Node >( current . neighbors . Count ); foreach ( var oldNeighbor in current . neighbors ) { Node newNeighbor ; if (! dict . TryGetValue ( oldNeighbor . val , out newNeighbor )) { newNeighbor = CloneVal ( oldNeighbor ); queue . Enqueue ( newNeighbor ); dict . Add ( newNeighbor . val , newNeighbor ); } newNeighbors . Add ( newNeighbor ); } current . neighbors = newNeighbors ; } return dict [ node . val ]; } private Node CloneVal ( Node node ) { return new Node ( node . val , new List < Node >( node . neighbors )); } }

1/* // 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; } } */ 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 e : node . neighbors ) { clone . neighbors . add ( cloneGraph ( e )); } return clone ; } }

1""" # Definition for a Node. class Node: def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] """ class Solution : def cloneGraph ( self , node : 'Node' ) -> 'Node' : visited = defaultdict () def clone ( node ): if node is None : return None if node in visited : return visited [ node ] c = Node ( node . val ) visited [ node ] = c for e in node . neighbors : c . neighbors . append ( clone ( e )) return c return clone ( node )

1/* // Definition for a Node. class Node { public: int val; vector<Node*> neighbors; Node() { val = 0; neighbors = vector<Node*>(); } Node(int _val) { val = _val; neighbors = vector<Node*>(); } Node(int _val, vector<Node*> _neighbors) { val = _val; neighbors = _neighbors; } }; */ 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 ( auto & e : node -> neighbors ) clone -> neighbors . push_back ( cloneGraph ( e )); return clone ; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem