Lesson 6 · Linear structures

Multidimensional Arrays

A multidimensional array represents data in a grid (like rows and columns). Despite being visualized in 2D or 3D, it is fundamentally stored in a single, flat, linear block of memory.

Flattening the Grid

Computer memory is a single linear sequence of addresses. To store a 3x3 matrix, the computer must flatten it into a 1D sequence.

In Row-Major Order, the entire first row is stored, followed by the entire second row, and so on. The math to find an element at (row, col) in a grid of width W is index = (row * W) + col.

Memory is always 1-dimensional
Row-major order is standard in C, C++, and Java
Column-major order is used in Fortran and MATLAB

Arrays of Arrays

Some languages (like Java) implement 2D arrays literally as an array of arrays. The outer array holds memory references (pointers) to several inner arrays.

While this allows for jagged arrays (where rows have different lengths), it means the rows are not guaranteed to be contiguous in memory, adding overhead to memory accesses.

Supports jagged/ragged structures
Requires following multiple pointers
Less cache-friendly than a flat block

Key reference

Terms, operations, and practical uses

Memory layout

Row-Major OrderStoring a 2D array in memory by placing the first entire row, then the second entire row, and so on.
Column-Major OrderStoring a 2D array by placing the first entire column, then the second. Used in Fortran and MATLAB.
FlatteningConverting 2D coordinates (row, col) into a 1D memory index using the formula: (row * width) + col.

Array structures

Dense ArrayA multidimensional array where a single block of memory is allocated for the entire grid.
Array of ArraysA 1D array where each element is a pointer to another 1D array. Java uses this for 2D arrays.
Jagged ArrayAn array of arrays where the inner arrays can have different lengths (e.g., row 0 has 3 elements, row 1 has 5 elements).

Traversal algorithms

Nested LoopsUsing an outer loop for rows and an inner loop for columns to visit every element in a 2D array.
Direction VectorsArrays like dx = [-1, 1, 0, 0] used to cleanly loop through a cell's neighbors in grid traversal (DFS/BFS).
Boundary CheckingEnsuring coordinates do not fall below 0 or exceed the array's width and height before accessing memory.

Code example

Flattening a 2x3 Grid

ROWS, COLS = 2, 3
grid = [[10, 20, 30], [40, 50, 60]]
flat_array = [0] * (ROWS * COLS)

for r in range(ROWS):
    for c in range(COLS):
        index = (r * COLS) + c
        flat_array[index] = grid[r][c]

print('Flat array:', flat_array)

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

int main() {
    int ROWS = 2, COLS = 3;
    int grid[2][3] = {{10, 20, 30}, {40, 50, 60}};
    vector<int> flat_array(ROWS * COLS);

    for (int r = 0; r < ROWS; r++) {
        for (int c = 0; c < COLS; c++) {
            int index = (r * COLS) + c;
            flat_array[index] = grid[r][c];
        }
    }
    return 0;
}

class Main {
    public static void main(String[] args) {
        int ROWS = 2, COLS = 3;
        int[][] grid = {{10, 20, 30}, {40, 50, 60}};
        int[] flat_array = new int[ROWS * COLS];

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                int index = (r * COLS) + c;
                flat_array[index] = grid[r][c];
            }
        }
    }
}

InputGrid: [[10, 20, 30], [40, 50, 60]]

OutputFlat array: [10, 20, 30, 40, 50, 60]

Example

Run the example step by step

Output

Cache Locality and Performance

Modern CPUs fetch memory in chunks (cache lines). When you read an element, nearby elements are also loaded into the fast CPU cache.

Because of row-major storage, iterating through a matrix row-by-row is significantly faster than iterating column-by-column, as you hit the cache sequentially rather than jumping around in memory.

Spatial locality dramatically speeds up reads
Row-by-row iteration is optimal
Column-by-column iteration causes cache misses

Common Operations

Multidimensional arrays are heavily used in image processing (pixels in X, Y), board games (chess boards), and dynamic programming tables.

Common algorithms include matrix multiplication, DFS/BFS grid traversal, and calculating prefix sums over 2D subgrids.

Ideal for spatial and grid-based data
Used for tabular memoization in DP
Traversal often uses direction arrays (e.g., dx, dy)