Skip to content
Back to Data StructuresAll lessons

Data Structures

Sparse Matrix

get or set one cell: O(1) on average, using a hash-map lookup. Space: O(k), where k is the number of non-zero entries, not rows times cols. A full scan, like summing every value: O(k), not O(rows times cols).

The idea, in plain English

A sparse matrix is like a star catalog, not a photograph of the whole night sky. A photograph records every single pixel, including all the empty black space. A star catalog only lists where the actual stars are, their coordinates and brightness. It treats everywhere else as 'nothing, obviously.' A sparse matrix does the same for a huge grid that's almost entirely zeros. It only records where the non-zero values live.

How it works

  1. 1Instead of a full rows x cols grid, keep a lookup keyed by (row, col) that only holds entries for non-zero values.
  2. 2get(row, col): look up that key. If you find it, return its value. If not, the cell is 0 by definition.
  3. 3set(row, col, value): if the value is 0, remove that key entirely. There's no point storing a zero. Otherwise, store or update it.
  4. 4To scan or total the matrix, loop only over the stored, non-zero entries. Never loop over every empty cell.

When you'd use it

Use a sparse matrix for huge grids that are almost entirely zero: scientific and engineering simulations, one-hot encoded machine-learning feature vectors, or graph connections where there are far fewer edges than possible node pairs.

Common beginner mistakes

  • Don't store an explicit 0 anyway. That defeats the entire point. Always treat 'missing from storage' as the zero value. Never store zero itself.
  • Don't reach for a sparse matrix when the data is mostly filled in. The overhead of a hash-map lookup per cell makes it slower than a plain 2D array, once most cells actually hold a value.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Cell (2,3): 9
Cell (0,0): 0
Cell (1,1): 0
Stored cells: 2
Sum: 11

See it in motion

Dense grid ↔ triplesSparse matrix · 5×5get or set one cell: O(1) on average, using a hash-map lookup. Space: O(k), where k is the number of non-zero entries, not rows times cols. A full scan, like summing every value: O(k), not O(rows times cols).

Ready. Press play — only non-zero cells become stored (row, col, value) triples.

25
Dense cells
0
Stored (non-zero)
25
Zeros skipped
0/5
Step
Just set / storedCleared (back to 0)Non-zero valueZero (not stored)

Not sure this is the right topic? See the learning paths → or where this leads →