Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Graphs

Adjacency matrix to adjacency list

Easy · Target 8 minutes · Graphs

A graph on n nodes, numbered 0 to n − 1, is given as an adjacency matrix: matrix[i][j] is 1 if there is an edge from i to j and 0 otherwise. The graph may be directed, so the matrix need not be symmetric.

Return its adjacency list: a list of n lists, where list i holds the nodes that i has an edge to, in increasing order. A node with no outgoing edges has an empty list.

Examples

InputOutputWhy
matrix = [[0,1,1,0],[1,0,0,1],[1,0,0,1],[0,1,1,0]][[1,2],[0,3],[0,3],[1,2]]A symmetric matrix: an undirected square 0–1–3–2–0.
matrix = [[0,1,0],[0,0,1],[1,0,0]][[1],[2],[0]]A directed cycle 0 → 1 → 2 → 0.
matrix = [[0,0],[0,0]][[],[]]Two nodes and no edges.

Constraints

  • 1 ≤ n ≤ 500
  • matrix is n × n
  • matrix[i][j] is 0 or 1, and matrix[i][i] = 0

Hints

Hint 1

Row i of the matrix describes exactly the edges leaving node i.

Hint 2

Scan each row from left to right and keep the column numbers where the entry is 1. They come out in increasing order without sorting.

Where people lose marks

  • Reading columns instead of rows, which gives incoming edges rather than outgoing ones on a directed graph.
  • Adding both (i, j) and (j, i) when the matrix is already symmetric, which lists every undirected edge twice.
  • Skipping nodes with no edges, so the output has fewer than n lists.
Console⌘/Ctrl + Enter runs

Write a solution and run it against the real test table.


Keep going

Preparing for a real process? Quant interview preparation, or book a free 20-minute call.