Skip to content

level 1 · Foundations

2D Arrays

The grid is a fiction. Memory is one flat line — and that's why row-major is fast.

9 min 60 XP

what is it

Start here

A 2D array looks like a grid: rows and columns, neat little boxes. That picture is a lie — a useful one, but a lie.

Memory is one long line. There are no rows. When you write a[2][3], the computer computes `row × COLS + col` — a single multiply and add — and jumps to that one spot in the flat line. That's it. Same O(1) jump as a 1D array, with one extra piece of arithmetic.

Once you see that, something that sounds like folklore becomes obvious. Walking a grid row by row reads memory in a straight line, so the CPU cache loads a chunk and you use all of it. Walking column by column jumps COLS positions every single step, skipping past the data the cache just fetched — so it reloads, constantly.

Same number of operations. Same Big-O. Measurably slower, sometimes by several times. This is the first place you'll meet the fact that Big-O is not the whole truth about speed.

real-life analogy

Picture it

A bookshelf written down as one long list

You describe a bookshelf to someone over the phone as one continuous list of books. The 'shelves' only exist because you both agreed that every 10 books is a new shelf. To find shelf 2, book 3, you count 2×10 + 3 = book 23. The shelves were never real — they were arithmetic.

interactive visualization

Watch it run

Watch each (row, col) become one flat index: r × 5 + c.

4 × 5 — but memory is one flat line of 20

c0c1c2c3c4
r0
0
1
2
3
4
r1
5
6
7
8
9
r2
10
11
12
13
14
r3
15
16
17
18
19

A 2D array looks like a grid. It isn't. Memory is one long line — the grid is a fiction, and the computer keeps it up with a single piece of arithmetic.

step 01/23

  • comparing
  • in final place
1// A 2D array is a lie. Memory is flat — it's one long row.
2const ROWS = 4, COLS = 5;
3const flat = new Array(ROWS * COLS);
4
5// The computer turns (r, c) into a single index:
6function at(r, c) {
7 return r * COLS + c; // row-major order
8}
9
10// So a[2][3] really means flat[2 * 5 + 3] = flat[13].
11
12// Walking it row by row is fast (memory is read in order):
13for (let r = 0; r < ROWS; r++) {
14 for (let c = 0; c < COLS; c++) {
15 visit(flat[at(r, c)]);
16 }
17}

variables right now

rows
4
cols
5
cells
20
comparisons 0moves 0

the dry run · every step, in words

23 steps

complexity

What it costs

best case
O(1) to read a cell
average
O(r × c) to scan
worst case
O(r × c)
extra memory
O(r × c)

Reading a[r][c] is O(1) — one multiply, one add, one jump. Scanning it all is O(rows × cols), which for a square grid is n². The row-major-versus-column-major difference doesn't change the Big-O at all, and can still make your code several times slower.

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n)
  • O(n²) · this one
input size →work →

common mistakes

Common traps

  • Mixing up a[row][col] and a[col][row].

    The single most common bug in grid code. Fix a convention — row first, always — and never deviate. Half of all 'my matrix is transposed' bugs are this.

  • Walking column by column on a big grid.

    Same Big-O, several times slower in reality, because each step jumps past the cached memory. Prefer row-major order — read memory the way it's laid out.

  • Creating rows that all point at the same array.

    In several languages, filling a grid with a shared row reference means writing to one row writes to all of them. Build each row separately.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+60 XP

01How does the computer find a[2][3] in a grid with 5 columns?

02Why is walking a grid row by row faster than column by column?

03What does this lesson teach about Big-O?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.