Skip to main content
All Questions

Clone a graph.

Medium
Unlock detailed company stats for this questionUpgrade

Given a node in a connected, undirected graph, return a deep copy of the graph. Each node has an integer val and a list of its neighbors.

A deep copy has the same structure as the original, but every node in it is new. No node or neighbor list in the copy can point back into the original graph.

Node values run from 1 to n, and you're given the node with value 1. The examples and tests describe a graph as an adjacency list, where adjList[i] lists the neighbors of the node with value i + 1. The tests turn your copy back into an adjacency list, so the expected output matches the input. If your copy reuses a node from the original graph, the tests report [[-1]].

Example 1

Input: adjList = [[2, 4], [1, 3], [2, 4], [1, 3]] Output: [[2, 4], [1, 3], [2, 4], [1, 3]] 1 --- 2 | | 4 --- 3

Node 1 is connected to nodes 2 and 4, node 2 to nodes 1 and 3, and so on.

Example 2

Input: adjList = [[]] Output: [[]]

The graph has a single node with no neighbors.

Constraints

  • The graph has between 0 and 100 nodes. An empty graph means node is null.
  • Each node's value is unique, from 1 to n.
  • There are no repeated edges and no edges from a node to itself.
  • The graph is connected, so every node can be reached from the given node.

Related courses

Course

Software Engineering Interview Prep

Land your dream software engineering role at Google, Amazon, Microsoft, Meta, Apple, and other top companies. Learn from mock interviews, frameworks, and advice from senior candidates—practice data structures, algorithms, system design, people management, behavioral interviews, and more.

Course

System Design Interviews

Learn how to answer the latest system design questions across product, infrastructure, and AI domains. Features in-depth video examples, written breakdowns, and helpful reference patterns. Watch senior engineers and managers answer these questions in mock interview videos.