FastPrepClone a Connected Graph

Clone a Connected Graph

Abridge logoAbridge● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

A firsthand Abridge report describes a disguised Clone Graph problem. For this executable adapter, a connected undirected graph with nodes 1..n is supplied as an adjacency list: adjacency[i] lists the neighbors of node i + 1.

Construct a deep copy by traversing the graph and return the copied graph in the same adjacency-list representation. Preserve each neighbor list's order. Return an empty matrix for an empty graph.

Function

cloneGraph(adjacency: int[][]) → int[][]

Examples

Example 1

adjacency = [[2,4],[1,3],[2,4],[1,3]]return = [[2,4],[1,3],[2,4],[1,3]]

The four-node cycle is traversed and copied without changing edge order.

Example 2

adjacency = [[]]return = [[]]

The isolated start node is copied.

Constraints

  • 0 <= n <= 100
  • Every neighbor is in 1..n.
  • The graph is undirected and connected when nonempty.
  • Neighbor lists contain no duplicate node.

More Abridge problems

See Abridge hiring insights
public int[][] cloneGraph(int[][] adjacency) {
  // Traverse and deep-copy the adjacency lists.
}
adjacency[[2,4],[1,3],[2,4],[1,3]]
expected[[2,4],[1,3],[2,4],[1,3]]
Checking account…