Convert a Matrix to a Sparse Matrix in C++

A sparse matrix is a special matrix in which the number of zero elements is higher than the number of non-zero elements.

In this tutorial, we will be converting a given matrix input into a sparse matrix output in C++. After completing this tutorial, you will have mastered the technique of converting a given matrix into a sparse matrix.

The user can provide the number of rows and columns and the value of matrix elements as the input. The output will be in the form of a list of [ row, column, value] where the first output denotes the row number, the second denotes the column number and the third denotes the value of that row and column. So without wasting any time, let’s get started.

Steps for converting the matrix to a sparse matrix

1. Variable Declaration:
– First of all, we declare variables to obtain input for the number of rows and columns in the matrix to be given by the user.

2. Matrix Storage:
– Subsequently, we declare a 2D matrix using a vector of vectors of integers to efficiently store the matrix.

3. Sparse Matrix Representation:
– A vector is then initialized to store a 3-valued tuple for each non-zero element. Each tuple contains information in the form of [row, column, value]. (Hint: We can do so by declaring a vector of pair<pair<int, int>, int> )

4. Iteration through Matrix Elements:
– Then, we iterate through each element of the matrix to identify non-zero entries. For every non-zero element, we store the row number, column number, and the value at that specific position.

5. Printing Sparse Matrix:
– Finally, we print the sparse matrix and its dimension, displaying the non-zero elements in the specified format.

The following code implementation follows the above steps to create an efficient representation of a sparse matrix by storing only non-zero elements along with their respective row and column indices.

C++ code implementation for converting matrix into sparse matrix

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

void printmat(vector<pair<pair<int, int>, int>> &sparse, vector<vector<int>> &matrix){ //function declared to print our sparse matrix output
    cout << "Given Matrix:\n";
    for(int i=0; i<matrix.size(); i++){             
        for(int j=0; j<matrix[0].size(); j++){ //iterating through the elements stored in matrix
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }

    cout << "\nSparse Matrix:\nDimension of sparse matrix = " << sparse.size()<< "x" << 3;
    cout << "Row" << " Column" << " Value\n";
    for( auto it: sparse){       //iterating through the elements stored in sparse matrix
        int row = it.first.first;
        int col = it.first.second;
        int val = it.second;
        
        cout<< row <<" "<< col <<" "<< val << endl;
    }
}


int main() {
    int r, c;
    cin >> r >> c; //Taking inputs for number of rows and columns
    vector<vector<int>> matrix (r, vector<int>(c, 0)); //Declaring a 2D matrix for storing
 the given matrix by user input
    
    vector<pair<pair<int, int>, int>> sparse; // Declaring a vector that holds 3 values 
for each index that will denote the row number, column number and value present there
    
    
    
    
    for(int i=0; i<r; i++){  // Nested for loops for storing the given matrix
        for(int j=0; j<c; j++){
            int a;
            cin>>a;
            matrix[i][j]=a;
        }
    }
    
    // we will be entering the matrix elements in the form of {{row, column}, value}.
    for(int i=0; i<r; i++){   // Nested loop for creating desired sparse matrix
        for(int j=0; j<c; j++){
            if(matrix[i][j]!=0){  // if the value at certain row and column is non zero, 
we store the row no., column no., and the value present there
                pair<pair<int, int>, int> temp;
                temp.first.first = i;  // row no.
                temp.first.second = j; // column no.
                temp.second = matrix[i][j]; // value at matrix[row][column]
                sparse.push_back(temp); // we push_back the [row, column, value] data
 into the sparse vector
             }
        }
    }
    
    printmat(sparse, matrix);   // calling the print function for printing the sparse matrix
    
    return 0;
}

Example:

Input :

4 5 
1 0 0 2 0 
0 0 3 0 0 
0 1 0 0 5 
0 0 0 0 4

Output:

Given Matrix: 
1 0 0 2 0
0 0 3 0 0 
0 1 0 0 5 
0 0 0 0 4 
Sparse Matrix:
Dimension of sparse matrix = 6x3 
Row Column Value 
0 0 1 
0 3 2 
1 2 3 
2 1 1 
2 4 5 
3 4 4

Time and Space Complexity:

Time Complexity: O(r*c)   (as we are iterating through each element of the given matrix of size(r x c) )

Space Complexity: O(r*c)  (as we are storing the given matrix by taking inputs)