Unit 1 · Foundation of DSA
Sparse Matrix
Learn sparse matrix in DSA, including definition, compact representation, triplet form, advantages, and C examples.
Introduction
A sparse matrix is a matrix in which most elements are zero.
Storing every zero wastes memory, especially when the matrix is large. So sparse matrices are stored in compact forms that keep only non-zero values.
Sparse matrix representation is an important example of using the right data structure to save memory.
Normal Matrix 0 0 7 0 0 0 5 0 0 Triplet Form Row Col Value 0 2 7 2 0 5
Why Sparse Matrix Matters
Saves Memory
Only non-zero values are stored.
Faster Processing
Algorithms can skip unnecessary zero values.
Real Applications
Used in graphs, scientific computing, and machine learning.
Good DSA Example
Shows how representation affects efficiency.
Table of Contents
What is a Sparse Matrix?
A matrix is called sparse when the number of zero elements is much greater than the number of non-zero elements.
There is no single fixed percentage rule for every textbook, but practically, if zeros dominate the matrix, sparse representation becomes useful.
Opposite concept: A matrix with many non-zero values is called a dense matrix.
Why Do We Need Sparse Matrix Representation?
A normal 2D array stores all values, including zeros. If a 1000 by 1000 matrix has only 100 non-zero elements, storing all 1,000,000 cells is wasteful.
- Reduces memory consumption.
- Improves performance for operations that depend only on non-zero values.
- Makes very large matrices practical to store.
Triplet Representation
In triplet form, each non-zero element is stored using three values: row index, column index, and value.
Some formats store the first row as metadata: total rows, total columns, and total non-zero elements.
- Row: row position of the non-zero value.
- Column: column position of the non-zero value.
- Value: actual non-zero data.
Applications of Sparse Matrix
Sparse matrices are common in domains where most relationships or values are missing or zero.
- Graph adjacency matrices with few edges.
- Recommendation systems.
- Scientific simulations.
- Search engines and document-term matrices.
- Machine learning feature matrices.
Normal Matrix vs Sparse Matrix
| Feature | Normal Matrix | Sparse Representation |
|---|---|---|
| Storage | Stores all elements | Stores mainly non-zero elements |
| Memory use | High for large matrices | Low when zeros dominate |
| Best for | Dense data | Mostly zero data |
| Access simplicity | Very simple | Requires representation logic |
C Program Example
This program prints the triplet form of a sparse matrix.
#include <stdio.h>
int main() {
int matrix[3][3] = {
{0, 0, 7},
{0, 0, 0},
{5, 0, 0}
};
printf("Row Col Value\n");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (matrix[i][j] != 0) {
printf("%d %d %d\n", i, j, matrix[i][j]);
}
}
}
return 0;
}
Output:
Row Col Value
0 2 7
2 0 5
Key Points
- Sparse matrix contains mostly zero values.
- Compact representation stores only useful non-zero data.
- Triplet form stores row, column, and value.
- Sparse matrices save memory in large low-density data.
Interview Tip
Before using sparse representation, compare the number of non-zero elements with total matrix size.
Common Beginner Mistakes
- Using sparse representation for dense matrices.
- Forgetting to store row and column positions.
- Mixing 0-based and 1-based indexing in triplet form.
Quick Revision
- Sparse = mostly zeros.
- Triplet = row, column, value.
- Useful when non-zero elements are few.
- Common in graph and ML data.
Summary
A sparse matrix is a memory-efficient representation for matrices with many zeros. By storing only non-zero values and their positions, it saves space and can improve processing efficiency.
