Adjacency matrix to adjacency list
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
| Input | Output | Why |
|---|---|---|
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.
Dry run on [[0,1,1,0],[1,0,0,1],[1,0,0,1],[0,1,1,0]]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 4→
Row 0: the 1s are in columns 1 and 2, so node 0's list is [1, 2].
-
Step 2 / 4→
Row 1: the 1s are in columns 0 and 3, so node 1's list is [0, 3].
-
Step 3 / 4→
Row 2: the 1s are in columns 0 and 3, so node 2's list is [0, 3].
-
Step 4 / 4→
Row 3: the 1s are in columns 1 and 2, so node 3's list is [1, 2]. Every row is read: the adjacency list is complete.
How to think about it
Row i of an adjacency matrix lists, column by column, whether i has an edge to each
node. Reading the row left to right and keeping the columns that hold a 1 gives the neighbours of i,
already in increasing order. Do that for every row.
The conversion costs O(n²) because every entry must be read, whatever the number of edges. It is worth it when the graph is sparse and the next step is a traversal: on the list, a traversal costs O(n + m) instead of O(n²).
Complexity. Time O(n²) · Space O(n + m) for the output
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def matrix_to_list(matrix):
# Row i lists the edges leaving i; reading it left to right keeps them sorted.
return [[j for j, x in enumerate(row) if x == 1] for row in matrix]#include <vector>
std::vector<std::vector<int>> solve(const std::vector<std::vector<int>>& matrix) {
const int n = matrix.size();
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (matrix[i][j] == 1) adj[i].push_back(j); // row i: edges leaving i
return adj;
}class Solution {
public int[][] matrixToList(int[][] matrix) {
int n = matrix.length;
int[][] adj = new int[n][];
for (int i = 0; i < n; i++) {
int count = 0;
for (int x : matrix[i]) if (x == 1) count++;
adj[i] = new int[count];
int k = 0;
for (int j = 0; j < n; j++) if (matrix[i][j] == 1) adj[i][k++] = j; // row i: edges leaving i
}
return adj;
}
}function matrixToList(matrix) {
// Row i lists the edges leaving i; reading it left to right keeps them sorted.
return matrix.map(row => {
const out = [];
for (let j = 0; j < row.length; j++) if (row[j] === 1) out.push(j);
return out;
});
}fn solve<const N: usize>(matrix: &[[i64; N]]) -> Vec<Vec<i64>> {
// Row i lists the edges leaving i; reading it left to right keeps them sorted.
matrix
.iter()
.map(|row| (0..N).filter(|&j| row[j] == 1).map(|j| j as i64).collect())
.collect()
}solve :: [[Int]] -> [[Int]]
-- Row i lists the edges leaving i; reading it left to right keeps them sorted.
solve matrix = [[j | (j, x) <- zip [0 ..] row, x == 1] | row <- matrix]
Variants to try
- Go the other way: build the matrix from an adjacency list in O(n² + m).
- Return the lists of incoming edges instead (the transpose of the graph).
- The matrix holds weights, with 0 meaning no edge: return lists of [neighbour, weight] pairs.
Next problems
The person everyone trusts
Find the one person who trusts nobody and is trusted by everyone else, by counting edges in and out of each node.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Easy12 minDoes an undirected graph contain a cycle?
Return true if the graph has a cycle: a search that meets a visited node by any edge but the one it came along has found one.
Open the problem →Write a solution and run it against the real test table.
Keep going
The person everyone trusts
Find the one person who trusts nobody and is trusted by everyone else, by counting edges in and out of each node.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Easy12 minDoes an undirected graph contain a cycle?
Return true if the graph has a cycle: a search that meets a visited node by any edge but the one it came along has found one.
Open the problem → GraphsThe pattern behind it
Grids, networks and dependencies are all graphs. Breadth-first search finds shortest paths, depth-first search and union-find find what is connected, Dijkstra handles weighted edges, and a queue of nodes with no remaining prerequisites gives an order.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.