Lesson 9 · Linear structures

Sparse Arrays

When an array contains millions of elements but only a few of them hold actual data (the rest being a default value like 0), standard arrays waste a massive amount of memory. Sparse arrays use alternative data structures to store only the non-default values.

The Problem with Empty Space

Suppose you need an array indexed by user IDs, and user IDs can be up to 2 billion, but you only have 5,000 users.

Allocating a standard array of 2 billion integers would consume 8 Gigabytes of RAM, 99.999% of which would just hold zeroes. This is a sparse array scenario.

Massive index ranges cause memory exhaustion
Most elements hold a default 'empty' value
Typical in massive matrices or ID mapping

Hash Map Representation

The most common way to implement a sparse array is using a Hash Map (or Dictionary). The array index becomes the key, and the data becomes the value.

If you want to read an index, you check the hash map. If the key exists, you return the value; if it doesn't, you return the default value (e.g., 0).

Keys are indices, values are data
Memory usage is proportional to actual elements
Access time is expected O(1), but slower than native arrays

Key reference

Terms, operations, and practical uses

Memory concepts

SparsityThe ratio of zero (or default) elements to total elements in a dataset. High sparsity means most data is empty.
Default ValueThe value assumed for any index that is not explicitly stored in the sparse representation (usually 0 or null).
OverheadThe extra memory required to store indices or keys. If a dataset isn't sparse enough, storing keys wastes more memory than a dense array.

Representations

Hash Map / DictionaryUsing the array index as a key. O(1) expected lookup, but has significant memory overhead per entry.
Coordinate List (COO)Storing a simple list of (index, value) tuples. Very compact, but requires O(N) or O(log N) search to find a specific index.
Compressed Sparse Row (CSR)A highly optimized format for 2D sparse matrices using three 1D arrays, enabling extremely fast matrix multiplication.

Applications

Adjacency MatricesRepresenting graphs. Social networks have billions of nodes but few connections per node, making dense matrices impossible.
Machine LearningTraining models on sparse features like one-hot encoded text data, where 99% of feature columns are zero.
Scientific ComputingSolving massive systems of linear equations (finite element analysis) where only local elements interact.

Code example

Sparse Array using Coordinate List (COO)

coo = []
coo.append((100, 5))
coo.append((999, 2))
coo.append((50, 9))

# Sort by index for binary search capabilities
coo.sort(key=lambda x: x[0])
print('Sorted COO:', coo)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<pair<int, int>> coo;
    coo.push_back({100, 5});
    coo.push_back({999, 2});
    coo.push_back({50, 9});

    sort(coo.begin(), coo.end());
    return 0;
}

import java.util.*;

class Main {
    static class Element implements Comparable<Element> {
        int index, value;
        Element(int i, int v) { index = i; value = v; }
        public int compareTo(Element other) { return this.index - other.index; }
    }
    public static void main(String[] args) {
        List<Element> coo = new ArrayList<>();
        coo.add(new Element(100, 5));
        coo.add(new Element(999, 2));
        coo.add(new Element(50, 9));
        
        Collections.sort(coo);
    }
}

InputSet index 100 to 5, index 999 to 2, index 50 to 9

OutputSorted COO: [(50, 9), (100, 5), (999, 2)]

Example

Run the example step by step

Output

List of Pairs (Coordinate List)

Another representation is a dense array (or list) containing objects or pairs: (index, value). This is often called COO (Coordinate) format.

This format is extremely memory efficient and fast to iterate over if you only care about the valid elements, but looking up a specific random index requires a linear search or binary search (if sorted).

Stores arrays of [index, value] tuples
Very fast for sequential processing
O(log N) lookup if kept sorted

Applications in Matrices

Sparse arrays are most famously used in 2D space as Sparse Matrices. Algorithms in machine learning, finite element analysis, and graph theory (adjacency matrices for sparse graphs) rely heavily on them.

Formats like CSR (Compressed Sparse Row) are highly optimized for performing matrix multiplication on massive datasets where most connections are zero.

Essential for large-scale graph processing
Used in scientific computing and ML
Saves both memory and CPU cycles by skipping zeroes