All problems
MediumGraphs

Clone Graph

metagoogleamazonbloomberguber

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).

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.

Examples

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

There are 4 nodes forming a cycle: 1-2-3-4-1. Each node is cloned with its neighbors correctly referencing the new cloned nodes, not the originals.

Example 2
Input
adjList = [[]]
Output
[[]]

The graph has a single node with val = 1 and no neighbors. The clone is a new node with val = 1 and an empty neighbors list.

Example 3
Input
adjList = []
Output
[]

The graph is empty (null input), so the output is also null/empty.

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.

Optimal complexity

Time

O(V + E)

Space

O(V)

One problem, two ways to prep

Choose between solo practice and interview simulation

Practice Mode keeps things simple with code + tests. AI Interview Mode adds voice, pressure, and a post-round score summary.

Try 5-Minute Audio InterviewAI Interview Mode