Multidimensional and Jagged Arrays

## The core idea An **array** is a fixed-size, indexed container of values of one type. A **multidimensional array** conceptually is a grid (2D), cube (3D), etc. Many languages (C, Fortran) implement a 2D array as one **contiguous** block of memory of size rows×columns, with the compiler computing the address `base + (i*columns + j)*elementSize`. That is a *true rectangular array*: every row is guaranteed the same length and laid out back-to-back. **Java does not have this.** In Java, the type `int[][]` literally means "an array whose element type is `int[]`" — an **array of arrays**, also called a *nested* or *jagged-capable* array. ## What that means concretely Write `int[][] a = new int[3][4];`. Java creates: - one **outer** array of length 3 whose element type is `int[]` (it holds 3 *references*), - three **inner** `int[]` arrays, each of length 4, - and stores a reference to each inner array in the outer array's slots. So `a` is a reference to the outer array. `a[0]`, `a[1]`, `a[2]` are each a reference to a separate `int[]` object. These three inner arrays are independent heap objects and are **not** required to sit next to each other in memory. Indexing `a[i][j]` is two steps: (1) read `a[i]` — follow a reference to get the i-th inner array; (2) index `[j]` into that inner array. That is **two pointer dereferences**, versus one address computation in a contiguous layout. ## Why "no true rectangular array" Because each row is an independent object, nothing forces the rows to be equal length. `new int[3][4]` happens to make them all length 4, but you can replace any row: `a[1] = new int[10];` is legal. The "rectangle" is only a convention, not a language guarantee. The lengths are queried per level: `a.length` is the number of rows (the outer length); `a[i].length` is the length of row i. ## Consequences 1. **Jagged arrays are free** — rows of different lengths are the natural case, not a special feature (see the dedicated jagged-array question). 2. **Sub-arrays can be shared/aliased** — `int[] row = a[1];` makes `row` and `a[1]` the same object; mutating one is seen through the other. 3. **Performance** — extra indirection plus rows scattered on the heap means worse **cache locality** (the CPU caches contiguous memory; jumping between far-apart rows causes more cache misses) than a flat contiguous array. 4. **Initialization** — a freshly `new int[3][4]` array has every element at the default (`0` for int, `null` for references, `false` for boolean, etc.). ## Higher dimensions The pattern recurses: `int[][][]` is an array of (arrays of (arrays of int)). `new int[2][3][4]` builds one outer length-2 array, two length-3 arrays, and six length-4 arrays — 9 array objects in total. ## When it matters For most code the convenience wins. For numeric-heavy, performance-critical work, practitioners often **flatten** to a single `int[]` of size rows*cols and index manually as `data[i*cols + j]` to recover the contiguous, cache-friendly C-style layout.