import java.util.ArrayList;
import java.util.List;
public class CompactSparseMatrix {
// A sparse matrix is a matrix in which the majority of elements are zero.
// To compact a sparse matrix, use a method to store only the non‑zero
// entries using a triplet representation (row, column, value).
// This reduces memory usage.
// Convert a sparse matrix into compact (triplet) form
public static List<List<Integer>> compactMatrix(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
// Count non-zero elements
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] != 0) {
count++;
}
}
}
// Compact matrix has 3 rows: row index, col index, value
List<List<Integer>> compact = new ArrayList<>();
compact.add(new ArrayList<>(count));
compact.add(new ArrayList<>(count));
compact.add(new ArrayList<>(count));
// Pre-fill lists with zeros
for (int i = 0; i < count; i++) {
compact.get(0).add(0);
compact.get(1).add(0);
compact.get(2).add(0);
}
int k = 0;
// Fill compact matrix
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] != 0) {
compact.get(0).set(k, i); // row
compact.get(1).set(k, j); // column
compact.get(2).set(k, matrix[i][j]); // value
k++;
}
}
}
return compact;
}
public static void main(String[] args) {
int[][] matrix = {
{0, 0, 3, 0, 8, 0, 0, 0, 0},
{0, 0, 5, 7, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 2, 6, 0, 0, 4, 0, 0, 0},
{0, 0, 0, 0, 9, 0, 0, 0, 0}
};
List<List<Integer>> compact = compactMatrix(matrix);
System.out.println("Compact matrix:");
for (int i = 0; i < 3; i++) {
for (int val : compact.get(i)) {
System.out.print(val + " ");
}
System.out.println();
}
}
}
/*
run:
Compact matrix:
0 0 1 1 1 3 3 3 4
2 4 2 3 6 1 2 5 4
3 8 5 7 1 2 6 4 9
*/
