Lesson 5 · Linear structures

Multidimensional Arrays

A multidimensional array is a convenient fiction. Memory is a single linear address space, so a grid must be flattened — and the mapping chosen, row-major or column-major, decides both how indexing works and how fast a loop runs.

Flattening the Grid

Memory is a one-dimensional sequence of addresses. There are no rows and no columns in hardware, so a 2-D array is a convention laid over a flat block, and the convention is a formula.

In row-major order — used by C, C++, Java, C#, and Python's NumPy by default — the rows are stored one after another. Row 0 occupies the first cols slots, row 1 the next cols, and so on. The address of element [r][c] is therefore base + (r × cols + c) × width.

That formula is the entire mechanism, and reading it carefully explains everything else on this page. Note that it needs the number of columns, not the number of rows — which is why in C you may omit the first dimension of a function parameter but never the second.

Because the position is computed rather than searched for, access to any element of a grid remains O(1), exactly as for a 1-D array. The dimensionality is a notational convenience; the machine does one multiplication and one addition.

The inverse conversion is occasionally useful: given a flat index i, the row is i / cols and the column is i % cols. This turns a 2-D traversal into a single loop, which is sometimes cleaner and is how a grid is stored in a 1-D array deliberately — a technique worth knowing, since it guarantees contiguity in languages that would otherwise give you an array of arrays.

Hardware has no rows — the grid is a formula over flat memory
Row-major: index = row × cols + col
The column count is needed for the arithmetic; the row count is not
Flat index i maps back as row i / cols, column i % cols

One Block, or a Table of Pointers

Two genuinely different implementations both present grid[i][j] syntax, and the difference has real consequences.

A true multidimensional array is a single contiguous block. int grid[3][4] in C allocates 12 integers in one run of memory, and the compiler applies the flattening formula directly. There is one allocation, one pointer, and the rows are guaranteed adjacent.

An array of arrays — sometimes called a jagged array — is a one-dimensional array of pointers, each pointing to a separately allocated row. This is what new int[3][4] produces in Java, and what a Python list of lists is. Accessing grid[i][j] requires two memory reads: one to fetch the row pointer, one to reach the element.

Three consequences follow. The rows are not contiguous with each other, so a scan across the whole grid jumps between unrelated regions and defeats prefetching. Each row costs a separate allocation plus its own object header. And the rows can have different lengths, which is occasionally useful — a triangular matrix wastes no space — but means grid[i].length may vary and must be checked per row rather than assumed.

For numerical work in Java this is a real performance issue, and the standard remedy is to allocate a single flat array of rows × cols and index it manually with the formula. It is less readable and measurably faster. In Python the same reasoning is why NumPy exists: a NumPy 2-D array is one contiguous buffer, while a list of lists is a table of pointers to scattered objects.

A related trap worth naming: initialising a Python grid as [[0] * cols] * rows creates one row object referenced rows times, so writing to grid[0][0] appears to modify every row. The correct form is a comprehension, [[0] * cols for _ in range(rows)], which builds a distinct list per row.

The two implementations behind the same syntax
	True 2-D array	Array of arrays
Memory	One contiguous block	Pointer table plus separate rows
Reads per access	One	Two — pointer, then element
Allocations	One	One per row, plus the table
Row lengths	Uniform	May differ (jagged)
Found in	C, C++, NumPy	Java, Python lists of lists

C and NumPy give one block; Java and Python lists give pointer tables
An array of arrays costs a second dereference per access
Jagged rows are possible but rows are no longer contiguous
[[0]*c]*r in Python aliases one row — use a comprehension

Loop Order Decides the Speed

This is the practically important consequence, and it can change the runtime of identical work by several times.

The CPU does not fetch single values from memory. It fetches cache lines, typically 64 bytes — sixteen 4-byte integers. It also prefetches ahead when it detects a sequential access pattern. Both mechanisms reward reading memory in the order it is laid out.

In row-major storage, consecutive elements of a row are adjacent in memory. So iterating with the row index outer and the column index inner walks straight through memory: one cache line fetch serves sixteen accesses, and the prefetcher stays ahead.

Swapping the loops — column outer, row inner — reads elements separated by cols × width bytes. Each access lands on a different cache line, so every one is a potential cache miss, and the prefetcher cannot help because the stride is large. The same number of operations can run three to ten times slower, purely from memory behaviour.

The rule to carry away: iterate in the order the array is stored. For row-major languages that means rows outside, columns inside. The compiler will sometimes fix this for you through loop interchange, but only when it can prove the transformation is safe, so it is not something to rely on.

This is also why naive matrix multiplication is slow — its innermost loop traverses one matrix down a column — and why the standard remedies are transposing the second matrix so both are read row-wise, or blocking (tiling) the computation so each tile fits in cache and is fully used before being evicted. Optimised BLAS libraries achieve their speed largely through this rather than through fewer arithmetic operations.

None of this changes the asymptotic complexity. Both loop orders are O(rows × cols). It is a constant factor, and it is a large one — a reminder that big-O describes growth and not speed.

CPUs fetch 64-byte cache lines and prefetch sequential patterns
Row-major favours rows outer, columns inner
Reversing the loops can cost 3–10× with identical operation counts
Transposing or tiling is why optimised matrix multiplication is fast

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.

Implementation

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];
        }
    }
    cout << "Flat array: [";
    for (size_t i = 0; i < flat_array.size(); i++) {
        if (i) cout << ", ";
        cout << flat_array[i];
    }
    cout << "]\n";
}

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];
            }
        }
        System.out.println("Flat array: " + java.util.Arrays.toString(flat_array));
    }
}

Watch it run

Step through it

Running on Grid: [[10, 20, 30], [40, 50, 60]]

Output

Read all 11 Steps

The grid is a convenient fiction grid = [[10, 20, 30], [40, 50, 60]] reads as 2 rows by 3 columns, but RAM is a single linear address space. Hardware has no notion of a second dimension, so the rows must be laid end to end.
Row-major: index = r × COLS + c Row-major order stores row 0 completely, then row 1. The mapping r × COLS + c converts any (row, column) pair into one flat offset, and COLS is the only thing the formula needs to know.
(0,0) → index 0 index = 0 × 3 + 0 = 0. Store 10 at the very front of the block.
(0,1) → index 1 index = 0 × 3 + 1 = 1, so store 20 in the next slot. Moving one column to the right advances exactly one position in memory — columns are the cheap direction to walk.
(0,2) → index 2 index = 0 × 3 + 2 = 2, so store 30 and row 0 is complete. The next write must jump to the start of row 1, which is where the multiplication in the formula earns its place.
(1,0) → index 3 index = 1 × 3 + 0 = 3. Store 40. Advancing one row skips a whole COLS-sized stride, which is why row changes are the expensive direction.
(1,1) → index 4 index = 1 × 3 + 1 = 4, so store 50. Row 1 is now filling the same way row 0 did, one contiguous slot at a time.
(1,2) → index 5 index = 1 × 3 + 2 = 5. Store 60. All six cells are placed and the 2D grid now occupies one contiguous run.
Read grid[1][2] back The formula runs in reverse for access: 1 × 3 + 2 = 5, and slot 5 holds 60. Indexing is pure arithmetic — no search, no pointer chasing, O(1) regardless of grid size.
Row-major scanning is cache-friendly Looping columns inside rows touches slots 0,1,2,3,4,5 in order, so each cache line fetch serves several elements. Swapping the loops touches 0,3,1,4,2,5 and can miss the cache on every access — the same work running many times slower on a large matrix.
Column-major is the other convention Fortran, MATLAB, and R store columns first, making the formula c × ROWS + r and laying this grid out as 10, 40, 20, 50, 30, 60. C, C++, Java, and NumPy default to row-major, so the layout must be known before any pointer arithmetic or flat-buffer interop.

Column-Major and Higher Dimensions

Column-major order stores columns contiguously instead of rows, with the address of [r][c] at base + (c × rows + r) × width. Fortran, MATLAB, R and Julia use it, largely for historical compatibility with Fortran's numerical libraries.

The optimal loop order inverts accordingly: in column-major languages, the column index goes outer and the row index inner. Code translated between the two families without adjusting the loops will be correct and slow, which is a genuinely common defect in ported numerical code.

It also matters at interface boundaries. Passing a matrix from Python to a Fortran-backed LAPACK routine requires either transposing it or telling the routine the layout — and NumPy tracks this explicitly, allowing an array to be in C order or F order, and reporting it in the flags attribute.

For higher dimensions the row-major formula generalises directly. For a 3-D array with dimensions [D1][D2][D3], the flat index of [i][j][k] is i × (D2 × D3) + j × D3 + k. The pattern is that each index is multiplied by the product of all dimensions to its right, and the rightmost index varies fastest.

The same rule then predicts the correct loop nesting for any rank: the last index should be the innermost loop, because it is the one that moves through adjacent memory.

A practical note on higher dimensions: their size grows multiplicatively, so a 1000 × 1000 × 1000 array of 8-byte doubles is 8 GB. Multidimensional arrays become impractical quickly, which is one reason sparse representations and other structures take over beyond two or three dimensions.

Finally, worth stating for exam purposes: the choice of layout never changes the complexity of an access, which is O(1) either way. It changes constants, interoperability, and which loop order is correct — nothing more.

Column-major (Fortran, MATLAB, R, Julia) inverts the optimal loop order
3-D row-major index is i·D2·D3 + j·D3 + k
Each index scales by the product of the dimensions to its right
The rightmost index varies fastest, so it belongs in the innermost loop