What are sparse arrays?

Key takeaways:
Sparse arrays are designed to efficiently store and process data structures with many zero values, improving space and time efficiency.
Instead of storing every element, sparse arrays only store the non-zero values, which reduces memory usage and computational complexity.
Matrix representation of sparse arrays uses three rows to store the row index, column index, and the value of non-zero elements.
Linked list representation of sparse arrays links nodes that store the row, column, value, and pointer to the next non-zero element, allowing dynamic insertion and removal.
Sparse arrays are ideal for applications where memory optimization is crucial, such as large-scale datasets or sparse matrices in scientific computing.

An array is a data structure that stores elements of the same data type in a continuous memory space. However, in many cases, arrays contain a large number of zero elements, which wastes memory. To solve this, we use sparse arrays, a specialized data structure for efficient data storage when most of the array’s elements are zero.

Representation of sparse arrays

Sparse arrays can be represented in two primary ways:

Method 1: Using a matrix

In this approach, we use a 2D matrix to represent our sparse array.

Rows: The matrix has three rows.

$1^{st}$ row: It stores the row number of non-zero elements.
$2^{nd}$ row: It stores the column number of non-zero elements
$3^{rd}$ 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

#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 array
    int 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 matrix
    int 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 number
                sparse[1][i] = c;   // Column number
                sparse[2][i] = A[r][c];   // Value
                i++;
            }
        }
    }
    // Printing our sparse array matrix
    cout << "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;
  }

#include <iostream>
using namespace std;
// Creating Node structure for the linked list
struct Node {
    int row;
    int column;
    int value;
    Node* next;
};
// Function to create a new node for the linked list
Node* 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 array
    for (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, value
                Node* newNode = createNode(r, c, A[r][c]);
                if (head == nullptr) {
                    head = newNode;
                    current = newNode;
                }
                else {
                    current->next = newNode;
                    current = current->next;
                }
            }
        }
    }
    // Printing the linked list
    cout << "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;
}

Practical use cases of sparse arrays

Sparse arrays are commonly used in fields such as:

Machine learning: Sparse matrices are often used in recommendation systems and natural language processing.
Image processing: Sparse arrays efficiently represent sparse image data.
Graph algorithms: Sparse matrices are used to store graphs with a large number of nodes and relatively few edges.

Performance benchmarks

Using sparse arrays results in significant performance improvements compared to simple arrays, especially when handling large datasets. The space complexity is reduced from $O(n×m)$ in simple arrays to $O(k)$ in sparse arrays, where $k$ is the number of non-zero elements.

To further enhance your knowledge and skills in coding interviews, we recommend a specially designed path, Educative 99. This path offers interactive lessons that give hands-on experience with coding problems and opportunities to test and refine your solutions.

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.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

1. What is a sparse array in programming?

A sparse array is a data structure that stores only the non-zero elements of an array, which reduces memory usage and increases efficiency when working with large datasets containing many zero values.

2. Why are sparse arrays used?

Sparse arrays are used to optimize memory and processing efficiency, especially when dealing with arrays where most of the elements are zero.

3. How are sparse arrays represented?

Sparse arrays can be represented using a matrix representation, where a 2D matrix stores the non-zero elements and their indexes, or using a linked list, where each node stores the position and value of non-zero elements.

4. What is the difference between a sparse array and a simple array?

A simple array stores all elements, including zeros, in a continuous memory space. A sparse array only stores non-zero elements, along with their positions, improving memory efficiency.

5. How do you implement a sparse array in C++?

You can implement a sparse array in C++ using either a matrix or a linked list to store the positions and values of the non-zero elements.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Simple Array	Sparse Array
It stores all the elements of the array.	It stores the non-zero elements of the array only.
The indexes of elements are contiguous and start at the first cell.	The indexes of non-zero elements are not contagious and might not start at the first cell.

What are sparse arrays?

What is a sparse array?

Why do we use sparse arrays?

Comparison of a sparse array and a simple array

Sparse Array vs. Simple Array

Representation of sparse arrays

Method 1: Using a matrix

Example

Code in C++

Method 2: Using a linked list

Example

Code in C++

Practical use cases of sparse arrays

Performance benchmarks

Conclusion

Frequently asked questions

1. What is a sparse array in programming?

2. Why are sparse arrays used?

3. How are sparse arrays represented?

4. What is the difference between a sparse array and a simple array?

5. How do you implement a sparse array in C++?