Lesson 144 of 250
133. Clone Graph
NeetCode: Clone Graph · LeetCode: 133. Clone Graph · Difficulty: Medium
Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Each node has an integer value and a list of neighbors.
Example
adjacency list: 1: [2, 4] 2: [1, 3] 3: [2, 4] 4: [1, 3]
Output: an identical graph made of brand-new nodesLeetCode's Node class has an int val and a List<Node> neighbors. A Node field holds a reference to an object (or null), so there are no wrapper types for a missing node. The Node class does not override equals or hashCode, so two nodes are equal only when they are the same object. The examples use a helper, build, that creates nodes 1 to n from LeetCode's adjacency list, where entry i lists the neighbor values of node i + 1. A second helper, describe, prints one line per node (ordered by value) with its neighbor values, so the output does not depend on traversal order.
The core requirement: when an old node is reached through a second path, reuse the copy already made instead of creating another. That needs a mapping from old node to new node.
Brute force: mapping kept as a list searched linearly
Run a BFS from the start node. A BFS visits nodes in order of distance from the start, using a queue. Each time the copy of an old node is needed, search a list of {old, copy} pairs, comparing nodes with == (reference equality). This is correct, but each lookup costs O(V). ArrayDeque is the queue: add inserts at the tail and poll removes from the head.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class Main {
static class Solution {
public Node cloneGraph(Node node) {
if (node == null) {
return null;
}
List<Node[]> pairs = new ArrayList<>(); // {old, copy}
Node start = new Node(node.val);
pairs.add(new Node[]{node, start});
Deque<Node> queue = new ArrayDeque<>();
queue.add(node);
while (!queue.isEmpty()) {
Node old = queue.poll();
Node copy = lookup(pairs, old);
for (Node nb : old.neighbors) {
Node nbCopy = lookup(pairs, nb);
if (nbCopy == null) {
nbCopy = new Node(nb.val);
pairs.add(new Node[]{nb, nbCopy});
queue.add(nb);
}
copy.neighbors.add(nbCopy);
}
}
return start;
}
private Node lookup(List<Node[]> pairs, Node old) {
for (Node[] p : pairs) {
if (p[0] == old) {
return p[1];
}
}
return null;
}
}
static class Node {
public int val;
public List<Node> neighbors = new ArrayList<>();
Node(int val) {
this.val = val;
}
}
// Builds the graph from LeetCode's adjacency list: adjList.get(i) holds the
// neighbor values of node i + 1. Returns node 1, or null for an empty list.
static Node build(List<List<Integer>> adjList) {
if (adjList.isEmpty()) {
return null;
}
List<Node> nodes = new ArrayList<>();
for (int i = 0; i < adjList.size(); i++) {
nodes.add(new Node(i + 1));
}
for (int i = 0; i < adjList.size(); i++) {
for (int nb : adjList.get(i)) {
nodes.get(i).neighbors.add(nodes.get(nb - 1));
}
}
return nodes.get(0);
}
// All nodes reachable from start, found with a BFS.
static Set<Node> reachable(Node start) {
Set<Node> seen = new HashSet<>();
if (start == null) {
return seen;
}
Deque<Node> queue = new ArrayDeque<>();
seen.add(start);
queue.add(start);
while (!queue.isEmpty()) {
for (Node nb : queue.poll().neighbors) {
if (seen.add(nb)) {
queue.add(nb);
}
}
}
return seen;
}
// One line per node, ordered by value: "val: [neighbor values]".
static String describe(Node start) {
Map<Integer, String> lines = new TreeMap<>();
for (Node n : reachable(start)) {
List<Integer> vals = new ArrayList<>();
for (Node nb : n.neighbors) {
vals.add(nb.val);
}
lines.put(n.val, n.val + ": " + vals);
}
return String.join("\n", lines.values());
}
public static void main(String[] args) {
Solution s = new Solution();
Node original = build(List.of(List.of(2, 4), List.of(1, 3), List.of(2, 4), List.of(1, 3)));
Node copy = s.cloneGraph(original);
System.out.println(describe(copy));
Set<Node> originals = reachable(original);
boolean shared = false;
for (Node n : reachable(copy)) {
shared |= originals.contains(n);
}
System.out.println("shares a node with the original: " + shared);
Node single = build(List.of(List.of()));
System.out.println(describe(s.cloneGraph(single)));
System.out.println(s.cloneGraph(null));
}
}1: [2, 4]
2: [1, 3]
3: [2, 4]
4: [1, 3]
shares a node with the original: false
1: []
nullThe program also checks that the copy shares no node with the original, which confirms that the copy is deep. Time: O(V * (V + E)), since each of the O(V + E) lookups scans up to V pairs. Space: O(V + E).
Optimal: old-to-new lookup table
Replace the pair list with a HashMap<Node, Node> from old node to copy. A lookup is now one hash lookup (O(1) on average), so the whole traversal is linear. HashMap.get returns null for a missing key, which marks a node that has no copy yet.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class Main {
static 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 old = queue.poll();
Node copy = copies.get(old);
for (Node nb : old.neighbors) {
Node nbCopy = copies.get(nb);
if (nbCopy == null) {
nbCopy = new Node(nb.val);
copies.put(nb, nbCopy);
queue.add(nb);
}
copy.neighbors.add(nbCopy);
}
}
return copies.get(node);
}
}
static class Node {
public int val;
public List<Node> neighbors = new ArrayList<>();
Node(int val) {
this.val = val;
}
}
// Builds the graph from LeetCode's adjacency list: adjList.get(i) holds the
// neighbor values of node i + 1. Returns node 1, or null for an empty list.
static Node build(List<List<Integer>> adjList) {
if (adjList.isEmpty()) {
return null;
}
List<Node> nodes = new ArrayList<>();
for (int i = 0; i < adjList.size(); i++) {
nodes.add(new Node(i + 1));
}
for (int i = 0; i < adjList.size(); i++) {
for (int nb : adjList.get(i)) {
nodes.get(i).neighbors.add(nodes.get(nb - 1));
}
}
return nodes.get(0);
}
// All nodes reachable from start, found with a BFS.
static Set<Node> reachable(Node start) {
Set<Node> seen = new HashSet<>();
if (start == null) {
return seen;
}
Deque<Node> queue = new ArrayDeque<>();
seen.add(start);
queue.add(start);
while (!queue.isEmpty()) {
for (Node nb : queue.poll().neighbors) {
if (seen.add(nb)) {
queue.add(nb);
}
}
}
return seen;
}
// One line per node, ordered by value: "val: [neighbor values]".
static String describe(Node start) {
Map<Integer, String> lines = new TreeMap<>();
for (Node n : reachable(start)) {
List<Integer> vals = new ArrayList<>();
for (Node nb : n.neighbors) {
vals.add(nb.val);
}
lines.put(n.val, n.val + ": " + vals);
}
return String.join("\n", lines.values());
}
public static void main(String[] args) {
Solution s = new Solution();
Node original = build(List.of(List.of(2, 4), List.of(1, 3), List.of(2, 4), List.of(1, 3)));
Node copy = s.cloneGraph(original);
System.out.println(describe(copy));
Set<Node> originals = reachable(original);
boolean shared = false;
for (Node n : reachable(copy)) {
shared |= originals.contains(n);
}
System.out.println("shares a node with the original: " + shared);
Node single = build(List.of(List.of()));
System.out.println(describe(s.cloneGraph(single)));
System.out.println(s.cloneGraph(null));
}
}1: [2, 4]
2: [1, 3]
3: [2, 4]
4: [1, 3]
shares a node with the original: false
1: []
nullRecording the copy in copies when it is created, before its neighbors are explored, stops the traversal from looping around a cycle. Time: O(V + E). Space: O(V) for the map and the queue, plus the O(V + E) output.
The cloneGraph(null) call returns null, which is LeetCode's answer for an empty graph.