This chapter explores sparse arrays. A sparse array is an array where nearly all of the elements have the same value (usually zero), and this value is a constant, known ahead of time.
In many fields of mathematics and engineering, sparse arrays (in particular, arrays that consist almost entirely of zeros) are quite common. Therefore, it is worthwhile to develop efficient methods for handling such arrays.
In this chapter, we'll explore one way to efficiently represent sparse arrays, and in chapter 4 we'll see how this representation can pay huge dividends, both in terms of space and time.
Note that the examples given in this chapter are all for two-dimensional arrays. However, it is possible to generalize the ideas presented here for arrays of higher dimension; this is left as an exercise.