Clone Graph (Adjacency Matrix)

MediumGraphsbfs/dfs copy

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an undirected graph with n nodes labeled 0 through n - 1, described by an n x n adjacency matrix adj. The entry adj[i][j] is 1 if there is an edge connecting node i and node j, and 0 otherwise. The graph is undirected, so the matrix is symmetric: adj[i][j] == adj[j][i], and a node never has an edge to itself (the diagonal is all 0). Return a **deep copy (clone)** of the graph, expressed as a brand-new n x n adjacency matrix that you build by **traversing** the graph rather than copying rows wholesale. Starting from node 0, walk every node reachable from it (using BFS or DFS) and, for each visited node, record its edges into the cloned matrix. Because the result is produced by traversal from node 0, edges belonging to a component that is **not reachable** from node 0 will not be discovered, and their rows in the clone remain all zeros. For the common case of a connected graph (and the empty graph), the returned matrix is identical in value to adj but is an independently allocated structure. If n == 0 (an empty matrix), return an empty matrix.

Examples

Input: adj = [[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]]
Output: [[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]]
A 4-cycle 0-1-2-3-0. The graph is connected, so BFS from node 0 reaches every node and rebuilds all edges. The returned matrix has the same values as the input but is a freshly built copy.
Input: adj = [[0,1],[1,0]]
Output: [[0,1],[1,0]]
Two nodes joined by a single edge. Traversal from node 0 visits node 1 and records the symmetric edge.
Input: adj = [[0,0],[0,0]]
Output: [[0,0],[0,0]]
Two isolated nodes with no edges. Node 1 is unreachable from node 0, but since it has no edges its cloned row is all zeros anyway, matching the input.

Constraints

  • `0 <= n <= 100` where `n` is the number of nodes
  • `adj` is an `n x n` matrix and each entry is either `0` or `1`
  • `adj[i][i] == 0` for all `i` (no self-loops)
  • `adj[i][j] == adj[j][i]` (the graph is undirected and the matrix is symmetric)
  • The returned matrix must be a newly allocated structure, not the same object references as the input

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.