A sparse array is an array that has few elements in it. For example, the array

0 0 0 0 6 0
0 1 0 0 0 0
0 0 3 0 0 0
0 0 0 0 0 4

would be considered a sparse array.

In the older days when space was a prime concern of programmers, sparse arrays were considered bad form because they held a lot of wasted data in order to organize a few points for clarity. In today's era of the $.50 a gigabyte hard drive, this is hardly the case, but nonetheless, the workaround for sparse arrays was quite elegant.

It involved keeping tabs on the specific elements via a special object. Information on the row, column, and elements to the right and below the selected element would give all of the info needed in a pinch. It was still searchable, but saved the necessary creation of a multi-dimensional array to record and retrieve data.

Today, with the advent of linked lists and non-indexed arrays, the sparse array has all but ceased to be a programming problem.