What is meant by Sparse Array?

Read

Discuss

A sparse array or sparse matrix is an array in which most of the elements are zero.

Characteristics of Sparse array:

The sparse array is an array in which most of the elements have the same value(the default value is zero or null).
Sparse matrices are those array that has the majority of their elements equal to zero.
A sparse array is an array in which elements do not have contiguous indexes starting at zero.
Sparse arrays are used over arrays when there are lesser non-zero elements. Sparse arrays require lesser memory to store the elements and the computation time can be saved.

Examples of Sparse array:

$\begin{bmatrix} 0 & 4 & 0 \\ 1 & 0 & 0\\ 0 & 3 & 0 \\\end{bmatrix}$

$\begin{bmatrix} 0 & 4 & 0 &0\\ 1 & 0 & 0 &2\\ 0 & 3 & 0 & 0\\ 0 & 0 & 9 & 0\\\end{bmatrix}$

$\begin{bmatrix} 0 & 0\\ 0 & 3 \\\end{bmatrix}$

Why sparse array is required over simple arrays to store the elements:

Storage: When there is the maximum number of zero elements and the minimum number of non-zero elements then we use a sparse array over a simple array as it requires less memory to store the elements. In the sparse array, we only store the non-zero elements.
Computation Time: In the sparse array we only store non-zero elements and hence, traversing only non-zero elements takes less computation time.

Representation of Sparse Array:

Sparse arrays can be represented in two ways:

Array Representation
Linked List Representation

1. Array Representation:

To represent a sparse array 2-D array is used with three rows namely: Row, Column, and Value.

Row: Index of the row where non-zero elements are present.
Column: Index of the column where the non-zero element is present.
Value: The non-zero value which is present in (Row, Column) index.

Array Representation of Sparse Array

2. Linked List Representation:

To represent a sparse array using linked lists, each node has four fields namely: Row, Column, Value, and Next node.

Linked List Representation of Sparse Array

Implementation of array representation of the sparse array:

Implementation of array representation of the sparse array

Below is the representation of the sparse array:

C++

// Implementation of array representation 
// of the sparse array
#include <iostream>
using namespace std;
 
int main()
{
    int sparse[4][4] = { { 0, 0, 7, 0 },
                         { 1, 0, 0, 0 },
                         { 2, 0, 5, 0 },
                         { 0, 8, 0, 4 } };
    int s = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            if (sparse[i][j] != 0)
                s++;
    int representsparse[3][s];
    int k = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            if (sparse[i][j] != 0) {
                representsparse[0][k] = i;
                representsparse[1][k] = j;
                representsparse[2][k] = sparse[i][j];
                k++;
            }
    cout << "Representation of Sparse array using arrays : "
            "\n";
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < s; j++)
            cout << " " << representsparse[i][j];
        cout << "\n";
    }
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG {
  public static void main(String[] args)
  {
    int[][] sparse = { { 0, 0, 7, 0 },
                      { 1, 0, 0, 0 },
                      { 2, 0, 5, 0 },
                      { 0, 8, 0, 4 } };
    int s = 0;
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++)
        if (sparse[i][j] != 0)
          s++;
    int[][] representsparse = new int[3][s];
    int k = 0;
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++)
        if (sparse[i][j] != 0) {
          representsparse[0][k] = i;
          representsparse[1][k] = j;
          representsparse[2][k] = sparse[i][j];
          k++;
        }
    System.out.print(
      "Representation of Sparse array using arrays : ");
    System.out.println();
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < s; j++)
        System.out.print(" "
                         + representsparse[i][j]);
      System.out.println();
    }
  }
}
 
// This code is contributed by lokeshpotta20.

Python3

# Implementation of array representation
# of the sparse array
sparse = [[0, 0, 7, 0],
          [1, 0, 0, 0],
          [2, 0, 5, 0],
          [0, 8, 0, 4]]
s = 0
for i in range(4):
    for j in range(4):
        if (sparse[i][j] != 0):
            s += 1
 
representsparse = [[0 for i in range(s)] for i in range(3)]
k = 0
for i in range(4):
    for j in range(4):
        if (sparse[i][j] != 0):
            representsparse[0][k] = i
            representsparse[1][k] = j
            representsparse[2][k] = sparse[i][j]
            k += 1
 
print("Representation of Sparse array using arrays : ")
 
for i in range(3):
    for j in range(s):
        print(representsparse[i][j], end=" ")
    print("")
 
    # This code is contributed by saurabh_jaiswal.

C#

using System;
 
public class GFG{
 
    static public void Main (){
 
        // initializing sparse array
       int [,] sparse= { { 0, 0, 7, 0 },
                         { 1, 0, 0, 0 },
                         { 2, 0, 5, 0 },
                         { 0, 8, 0, 4 } };
    int s = 0;
    for (int i = 0; i < 4; i++){
        for (int j = 0; j < 4; j++){
            if (sparse[i,j] != 0)
                s++;
        }
    }
    int [,]representsparse =new int[3, s];
    int k = 0;
    for (int i = 0; i < 4; i++){
        for (int j = 0; j < 4; j++){
            if (sparse[i,j] != 0) {
                representsparse[0,k] = i;
                representsparse[1,k] = j;
                representsparse[2,k] = sparse[i,j];
                k++;
            }
        }
    }
            for (int i = 0; i < 3; i++) {
        for (int j = 0; j < s; j++){
        Console.Write(representsparse[i,j]+" ");
            }
            Console.WriteLine();
            }
    }}

Javascript

<script>
// Implementation of array representation 
// of the sparse array
 
 
    let sparse =[[ 0, 0, 7, 0 ],
                         [ 1, 0, 0, 0 ],
                         [ 2, 0, 5, 0 ],
                         [ 0, 8, 0, 4 ] ];
    let s = 0;
    for (let i = 0; i < 4; i++)
        for (let j = 0; j < 4; j++)
            if (sparse[i][j] != 0)
                s++;
    let representsparse[3][s];
    let k = 0;
    for (let i = 0; i < 4; i++)
        for (let j = 0; j < 4; j++)
            if (sparse[i][j] != 0) {
                representsparse[0][k] = i;
                representsparse[1][k] = j;
                representsparse[2][k] = sparse[i][j];
                k++;
            }
    document.write("Representation of Sparse array using arrays : ");
            "\n";
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < s; j++)
           document.write(" " + representsparse[i][j]);
        document.write("\n");
    }
    </script>

Output

Representation of Sparse array using arrays : 
 0 1 2 2 3 3
 2 0 0 2 1 3
 7 1 2 5 8 4

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

Last Updated : 27 Oct, 2022