What are sparse arrays?
An array is a data structure that stores elements of the same data type in a contagious memory space.
A sparse array is a data structure that is designed to efficiently store and manipulate arrays where the majority of the elements have a value of zero.
Why do we use sparse arrays?
A sparse array data structure is more time and space efficient. In this, we only store non-zero values of the array minimizing the space complexity, and traverse only the non-zero elements in the array, minimizing the time complexity.
Difference between a sparse array and a simple array
The key differences between a simple array and a sparse array data structure are as follows:
Simple Array | Sparse Array |
It stores all the elements of the array. | It stores the non-zero elements of the array only. |
The indices of elements are contagious and starts with zero. | The indices of non-zero elements are not contagious and might not start with zero. |
Representation of sparse arrays
There are two representations of sparse arrays:
Using a matrix
In this approach, we use a 2D matrix to represent our sparse array.
Rows: The matrix has three rows.
1st row: It stores the row number of non-zero elements.
2nd row: It stores the column number of non-zero elements
3rd row: It stores the value of non-zero elements.
Columns: The total number of columns in the matrix equals the total number of non-zero elements.
Example
Let's suppose we have a sparse array A:
In array A, the first non-zero element 1 is located in row 0 and column 0. Therefore, in the array representation, its row number is 0, column number is 0, and value is 1.
The complete representation of sparse array A in a 2D matrix will be:
Code in C++
The following code demonstrates how to represent our sparse array A in a matrix:
#include <iostream>using namespace std;int main(){int A[3][3] = {{1, 0, 2},{0, 4, 0},{0, 0, 0}};// Finding the total number of non-zero elements in the original arrayint count_nonzero = 0;for (int r = 0; r < 3; r++){for (int c = 0; c < 3; c++){if (A[r][c] != 0){count_nonzero++;}}}// Create a sparse array using a 2D matrixint sparse[3][count_nonzero];int i = 0;for (int r = 0; r < 3; r++){for (int c = 0; c < 3; c++){if (A[r][c] != 0){sparse[0][i] = r; // Row numbersparse[1][i] = c; // Column numbersparse[2][i] = A[r][c]; // Valuei++;}}}// Printing our sparse array matrixcout << "Sparse array: " << endl;for (int r = 0; r < 3; r++){for (int c = 0; c < count_nonzero; c++){cout << " " << sparse[r][c];}cout <<endl;}return 0;}
Using a linked list
In this approach, we use a linked list to represent our sparse array.
Each node in the linked list has four attributes:
Row number: It stores the row number of our non-zero element.
Column number: It stores the column number of our non-zero element
Value: It stores the value of our non-zero element
Next node pointer: It stores the pointer to the next node.
Example
Let's suppose we have a sparse array A:
In array A, the first non-zero element 1 is located in row 0 and column 0. Therefore, in the linked list representation, the node corresponding to this element will have a row number of 0, a column number of 0, and a value of 1. The next attribute of this node will be pointing to the node representing the next non-zero element in our array.
The complete representation of array A in linked list will be:
Code in C++
The following code demonstrates how to represent sparse array A in a linked list:
#include <iostream>using namespace std;// Creating Node structure for the linked liststruct Node {int row;int column;int value;Node* next;};// Function to create a new node for the linked listNode* createNode(int r, int c, int v) {Node* newNode = new Node;newNode->row = r;newNode->column = c;newNode->value = v;newNode->next = nullptr;return newNode;}int main() {int A[3][3] = {{1, 0, 2},{0, 4, 0},{0, 0, 0}};Node* head = nullptr;Node* current = nullptr;// Traversing the original arrayfor (int r = 0; r < 3; ++r) {for (int c = 0; c < 3; ++c) {if (A[r][c] != 0) {// Creating a new node with row number, column number, valueNode* newNode = createNode(r, c, A[r][c]);if (head == nullptr) {head = newNode;current = newNode;}else {current->next = newNode;current = current->next;}}}}// Printing the linked listcout << "Sparse array: " << endl;Node* tempNode = head;while (tempNode != nullptr) {cout << "Row: " << tempNode->row << ", Column: " << tempNode->column << ", Value: " << tempNode->value << endl;tempNode = tempNode->next;}return 0;}
Conclusion
Sparse arrays offer an efficient solution for storing and manipulating data with many zero elements. By representing only non-zero elements and their positions, they minimize memory usage and improve computational efficiency. They are particularly useful in scenarios where memory optimization is crucial, such as working with large-scale datasets.
