How Would You Represent a Sparse Matrix Efficiently?
Learn how to efficiently represent a sparse matrix using COO and CSR formats instead of a memory-wasting dense array.
Expected Interview Answer
A sparse matrix — one where the vast majority of entries are zero — should be stored by recording only the non-zero values and their coordinates, using structures like COO (coordinate list of row, column, value triples), CSR (compressed sparse row, storing row pointers, column indices, and values), or a dictionary/hash-map keyed by (row, col), instead of a full dense 2D array that wastes memory on zeros.
A dense 2D array always costs O(rows * cols) memory regardless of content, which becomes wasteful when a matrix is, say, 99% zeros, as is common in graph adjacency matrices, scientific simulations, and one-hot encoded ML features. COO simply stores three parallel arrays or a list of (row, col, value) triples, which is easy to build incrementally but slow for row-wise operations. CSR compresses that further by storing one row-pointer array marking where each row's entries start in the column-index and value arrays, which gives fast row slicing and is the standard format for sparse matrix-vector multiplication in libraries like SciPy. The right choice depends on the access pattern: COO for easy construction and format conversion, CSR for fast row access and matmul, CSC (compressed sparse column) for fast column access, and a plain hash map for extremely sparse, randomly-accessed matrices where even COO's overhead isn't justified.
- Memory scales with the number of non-zero entries, not rows * cols
- CSR/CSC enable fast, cache-friendly row or column slicing
- COO is simple to build incrementally from triples
- Standard format for efficient sparse matrix-vector multiplication in libraries like SciPy
AI Mentor Explanation
A dense matrix is like printing a full head-to-head results grid for every team against every other team in a 50-team tournament, even though most pairs never actually played, leaving the grid mostly blank. A sparse representation instead keeps a short list of only the pairs that did play, recording (team A, team B, result) triples, skipping every blank cell entirely. This is exactly COO: a list of coordinate triples instead of a mostly-empty grid. When you need to quickly pull every result for one specific team, you'd compress that list into row-grouped blocks — the cricket-board equivalent of CSR — so you jump straight to that team's section instead of scanning the whole list.
Step-by-Step Explanation
Step 1
Recognize sparsity
If the fraction of non-zero entries is small (rule of thumb: well under ~10-30%), a dense array wastes memory.
Step 2
Choose COO for construction
Store (row, col, value) triples as you discover non-zero entries; simple to build and convert from.
Step 3
Compress to CSR for row-heavy access
Sort by row, then store a row-pointer array plus parallel column-index and value arrays for O(nnz-per-row) row slicing.
Step 4
Use CSC or a hash map for other access patterns
CSC for fast column access; a dict keyed by (row, col) for very sparse, randomly-accessed matrices with frequent point lookups.
What Interviewer Expects
- Recognize that a dense array wastes O(rows*cols) memory regardless of content
- Name at least two sparse formats (COO and CSR, ideally CSC too) and what each is optimized for
- Explain the tradeoff: COO easy to build vs CSR fast for row operations
- Give a real-world example: graph adjacency matrices, one-hot ML features, scientific computing
Common Mistakes
- Defaulting to a dense 2D array/list-of-lists for a matrix that is mostly zeros
- Not knowing CSR/CSC trade insertion speed for fast row/column access
- Forgetting a plain dict/hash map keyed by (row, col) is a valid, simple sparse option
- Assuming sparse formats are always faster — dense arrays win when the matrix is not actually sparse
Best Answer (HR Friendly)
“For a sparse matrix I only store the values that are actually non-zero, along with their coordinates, instead of wasting memory on a full grid of mostly zeros. Depending on whether I am building the matrix or doing fast row-based math on it, I would pick a simple coordinate list or a more compressed row-based format like CSR, which is what libraries like SciPy use under the hood.”
Code Example
# Dense: wastes memory on zeros, O(rows * cols) regardless of content
dense = [[0] * 10000 for _ in range(10000)] # 100M cells, mostly zero
# Sparse COO: store only non-zero entries as (row, col, value) triples
sparse_coo = [
(12, 4801, 3.5),
(7, 12, 1.0),
(9999, 0, 42.0),
] # memory scales with number of non-zero entries, not rows * cols
def coo_get(entries, row, col, default=0):
for r, c, v in entries:
if r == row and c == col:
return v
return default
# In practice, use scipy.sparse for real workloads:
# from scipy.sparse import csr_matrix
# csr_matrix((data, (rows, cols)), shape=(10000, 10000))Follow-up Questions
- How would you convert a COO matrix to CSR format efficiently?
- Why is CSR preferred over COO for sparse matrix-vector multiplication?
- How would you represent a sparse matrix if you also needed fast column slicing?
- What is the memory complexity of a sparse matrix representation in terms of non-zero entries?
MCQ Practice
1. What is the main problem with using a dense 2D array for a sparse matrix?
A dense array allocates space for every cell whether or not it holds a meaningful value, wasting memory when most entries are zero.
2. What does CSR (compressed sparse row) format optimize for?
CSR uses a row-pointer array to mark where each row's non-zero entries start, making row slicing and row-based operations efficient.
3. Which sparse format is simplest to build incrementally while scanning data?
COO just appends (row, col, value) triples as they are discovered, making it the easiest format to construct before converting to CSR/CSC.
Flash Cards
What does a sparse matrix representation store, unlike a dense array? — Only the non-zero values and their (row, col) coordinates, not every cell.
What is COO format? — A list of (row, col, value) triples for each non-zero entry; simple to build.
What is CSR format optimized for? — Fast row-wise access and row-based operations, via a row-pointer array plus column-index and value arrays.
Name a real-world use case for sparse matrices. — Graph adjacency matrices, one-hot encoded ML features, or scientific simulation grids.