← Matrices · guided lesson
Matrices & Simulation
the story
Row-major layout & index maths
Every tool here exists because something was too slow or broke without it. Here is what.
A grid has rows and columns, but memory is one long line of numbered slots. Every language must decide which cell comes next.
FORTRAN (IBM, 1957) chose columns: the 1957 paper's address formula for A(I, J, K) multiplies J by the size of the first dimension, so the first subscript moves fastest.
C, which grew up at Bell Labs between 1969 and 1973, chose rows: the C standard says arrays are stored in row-major order, the last subscript varying fastest.
Java (1996) made int[][] an array of references to row arrays (JLS chapter 10). Each row is its own int[], so walking along a row is the fast direction.
the problem it solved
Turning a two-dimensional table into addresses in one-dimensional memory, with one multiply and one add per lookup.
why it matters: without it
Every grid would need its own map from (row, col) to memory, and image buffers, flat visited arrays and cell ids like r * cols + c would all be ad hoc.
sources: Backus et al. — The FORTRAN Automatic Coding System (Western Joint Computer Conference, 1957), index formula for A(I, J, K) ↗ · ISO C committee draft N1570, §6.5.2.1 ¶3: "arrays are stored in row-major order" ↗ · Dennis Ritchie — The Development of the C Language (HOPL-II, 1993) ↗ · Java Language Specification (SE 17), Chapter 10: Arrays ↗
also in this chapter: Direction arrays & boundary walks · Rotation by transpose + reverse · In-place markers (row 0 / column 0, spare bits) · Cellular automata & generation updates
the idea
The idea in 30 seconds
A matrix looks like a grid, but memory is one long line. So every grid is stored row after row, and cell (r, c) is number r × cols + c on that line.
With that index maths and a small table of directions, you can walk a grid in any order: rows, rings, diagonals, zigzags, neighbours.
Most grid questions are careful simulations: change the cells in place without destroying information you still need.
picture this
Your laptop screen. 1920 × 1080 pixels look like a grid, but the image sits in RAM as one long run of numbers, line after line. Java's BufferedImage.getRGB hands pixels back in one int[], with pixel (x, y) at index y × scansize + x (with its offsets at 0): row y first, then column x. Rotate a photo, blur it, or count Minesweeper neighbours, and you are doing this chapter's index maths.
watch it
Row-major: one grid, one long line
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Row-major: one grid, one long line
Each row becomes one unbroken run of the flat array. (r, c) lands at r × cols + c, and i / cols, i % cols takes you back.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Spiral order with four shrinking walls
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Spiral order with four shrinking walls
Walk a side, push that wall in. The two guards stop a single leftover row or column from being walked twice.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 9
Read it once. Say it out loud once. Bas.
Row-major: cell (r, c) is index r * cols + c of one long line. The way back is r = i / cols, c = i % cols. Always divide by cols, never by rows.
key idea 2 of 9
Read it once. Say it out loud once. Bas.
Java's `int[][]` is an array of row arrays. Each row is its own int[]. Loop r outside and c inside, so you read each row in memory order.
key idea 3 of 9
Read it once. Say it out loud once. Bas.
Direction arrays: keep moves in a table like {{-1,0},{0,1},{1,0},{0,-1}} (clockwise). Turning right is (d + 1) % 4. Check the bounds before you read a neighbour.
key idea 4 of 9
Read it once. Say it out loud once. Bas.
Layer by layer: four walls (top, bottom, left, right). Walk one side, push that wall inwards, and stop when the walls cross.
key idea 5 of 9
Read it once. Say it out loud once. Bas.
Rotation = two mirrors: a clockwise quarter turn sends (r, c) to (c, n − 1 − r). Transpose, then reverse every row. O(1) extra space.
key idea 6 of 9
Read it once. Say it out loud once. Bas.
Mark first, write later: when one cell's change affects a whole row or column, record what must happen, then do it. Row 0 and column 0 can be the notebook.
key idea 7 of 9
Read it once. Say it out loud once. Bas.
Two states in one cell: bit 0 = the value now, bit 1 = the value next. Read & 1, plan with |= 2, finish with >>= 1.
key idea 8 of 9
Read it once. Say it out loud once. Bas.
Simulation discipline: read only from the old state, write only to the new one. Mixing them is the classic Game of Life bug.
key idea 9 of 9
Read it once. Say it out loud once. Bas.
Rectangles, not squares: test 1 × 1, 1 × n, n × 1 and 3 × 4. Most grid bugs hide in a single leftover row or column.
spot the pattern
When you see this, think this
"Spiral order", "layer by layer", "ring"
Four shrinking walls, with guards for a single leftover row or column
"Rotate the image 90°" in place, n × n
Transpose, then reverse every row
"If a cell is 0, set its whole row and column to 0"
Mark first, write later; row 0 and column 0 as markers
"All cells update at the same time", "next generation", "next state"
Read old, write new: a copy, or two bits per cell
+4 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Un-flattening with
i / rowsinstead ofi / cols. It only works by luck on square grids. grid.clone()copies only the outer array. The rows are shared, so your "copy" changes the original.
quick check
One question. No pressure.
In a 3 × 5 grid stored row-major, which cell is at index 11?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Rotate Image
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Cell (r, c) of an m × n grid, row-major: its flat index? And the way back?
Question 1: Cell (r, c) of an m × n grid, row-major: its flat index? And the way back?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.