// 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
fun compactMatrix(matrix: List<List<Int>>): List<List<Int>> {
val rows = matrix.size
val cols = matrix[0].size
// Count non-zero elements
val count = (0 until rows).sumOf { i ->
(0 until cols).count { j -> matrix[i][j] != 0 }
}
// Compact matrix has 3 rows: row index, col index, value
val compact = List(3) { MutableList(count) { 0 } }
var k = 0
// Fill compact matrix
for (i in 0 until rows) {
for (j in 0 until cols) {
if (matrix[i][j] != 0) {
compact[0][k] = i // row
compact[1][k] = j // column
compact[2][k] = matrix[i][j] // value
k++
}
}
}
return compact
}
fun main() {
val matrix = listOf(
listOf(0, 0, 3, 0, 8, 0, 0, 0, 0),
listOf(0, 0, 5, 7, 0, 0, 1, 0, 0),
listOf(0, 0, 0, 0, 0, 0, 0, 0, 0),
listOf(0, 2, 6, 0, 0, 4, 0, 0, 0),
listOf(0, 0, 0, 0, 9, 0, 0, 0, 0)
)
val compact = compactMatrix(matrix)
println("Compact matrix:")
for (i in 0 until 3) {
println(compact[i].joinToString(" "))
}
}
/*
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
*/
