Question

How to compact a sparse matrix in TypeScript

Answer 1

// 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
function compactMatrix(matrix: number[][]): number[][] {
    const rows: number = matrix.length;
    const cols: number = matrix[0].length;

    // Count non-zero elements
    let count: number = 0;
    for (let i: number = 0; i < rows; i++) {
        for (let j: number = 0; j < cols; j++) {
            if (matrix[i][j] !== 0) {
                count++;
            }
        }
    }

    // Compact matrix has 3 rows: row index, col index, value
    const compact: number[][] = [
        new Array(count).fill(0),
        new Array(count).fill(0),
        new Array(count).fill(0)
    ];

    let k: number = 0;

    // Fill compact matrix
    for (let i: number = 0; i < rows; i++) {
        for (let j: number = 0; j < cols; j++) {
            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;
}

const matrix: number[][] = [
    [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]
];

const compact = compactMatrix(matrix);

console.log("Compact matrix:");
for (let i: number = 0; i < 3; i++) {
    console.log(compact[i].join(" "));
}


/*
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 

*/

 

70+ SQL courses for beginners and professionals