Foundations · Two-dimensional arrays

A matrix is one flat line, folded into rows

Q: Give me the address of M[r][c].

base + (r × n + c) × size , for a 0-based row-major array with n columns. For a 3 × 3 array of 4-byte ints, M[1][2] sits at base + (1×3 + 2)×4 = base + 20 . It is one multiply and one add, which is exactly why cell access is O(1) and not a search.

Q: You have a flat index k into a 1-D array. How do you read it as a grid?

r = k / n using integer division and c = k % n . With n = 3 and k = 7 you get r = 2 and c = 1, the middle cell of the last row. This is how you simulate a matrix inside a plain 1-D array, which is what most high-performance libraries actually do.

Q: How do you transpose a square matrix in place?

Swap M[r][c] with M[c][r] for every pair where c > r . Starting the inner loop at c = r + 1 is the whole trick: start it at 0 and you swap each pair twice, which puts the matrix back exactly as it was. An n × n transpose is n(n−1)/2 swaps and O(1) extra space; a non-square matrix cannot be done in place because the result has different dimensions.

Memory has no rows. M[r][c] is arithmetic — cell number r × n + c in a single block. Learn that one formula and the nested loops, the traversal order and the transposes all fall out of it.

Walk the same 3 × 3 two different ways →

M[r][c]the pair you write in code

→

r × n + cthe one flat position it actually means

→

Outer loop = rpicks which row you are standing on

→

Inner loop = cwalks that row, column 0 to n − 1

01 The idea

Two indices, one straight line of memory

A 2-D array is a block of values you reach with two numbers instead of one. You picture a grid: m rows across n columns, and M[r][c] is the cell where row r meets column c. Memory does not have that shape. It is one long line of storage, so the language has to fold your grid into that line, and it folds it row by row. Row 0 is laid down first, then row 1 immediately after it, then row 2. That layout is called row-major order.

Once you can see the fold, the nested loop writes itself. The outer loop chooses which row you are on. The inner loop walks that row from column 0 to column n − 1, and then the outer loop moves you down one. Swap those two loops and you still touch all m × n cells, but you meet them in a different order — and a surprising number of interview questions are really about that order.

Memory is a straight line. M[r][c] means cell number r × n + c in that line, where n is the column count. The outer loop chooses the row, the inner loop walks it left to right.

Dimensions m × nm rows by n columns, rows named first. Row index r runs 0 to m − 1, column index c runs 0 to n − 1. A 3 × 4 matrix has 3 rows of 4 cells each.

Row-major orderWhole rows are stored one after another. M[r][c] lands at flat position r × n + c, so the last cell of a row and the first cell of the next are neighbours in memory.

Jagged arrayA 2-D array whose rows have different lengths. Java's int[][] and a Python list of lists allow it; a C int[3][4] does not. With jagged rows there is no single n.

02 Worked example

Row sums of a 3 × 3, one cell at a time

Take the matrix 4 1 3 / 2 5 0 / 6 2 1 — three rows, three columns, and it stays on screen for the rest of this lesson. The job is one number per row: the sum of that row's three cells. Walk it in row-major order, which means finish a row before you start the next, and keep a running sum that resets when the row changes. The rose cells are the nine values being read; the green row at the bottom is what you end up storing.

r = 04130+4 = 4 → 4+1 = 5 → 5+3 = 8, so rowSum[0] = 8

r = 12500+2 = 2 → 2+5 = 7 → 7+0 = 7, so rowSum[1] = 7

r = 26210+6 = 6 → 6+2 = 8 → 8+1 = 9, so rowSum[2] = 9

rowSum[ ]879one answer per row, in row order · 8+7+9 = 24

Two things to carry forward. First, the running sum belongs to the outer loop: it is created once per row, reset before the inner loop starts, and stored when the inner loop ends. Move that reset into the inner loop and every row sum collapses to the last cell of its row — you would store 3, 0, 1. Move it above the outer loop and the sum never restarts, so you store running totals 8, 15, 24: still three numbers, but each one is every row up to that point, and only the last is the grand total 24. Second, look at the order the nine cells were read: 4, 1, 3, 2, 5, 0, 6, 2, 1. That is exactly the order they sit in memory, because the matrix was stored row after row.

03 Mechanics

Same nine cells, two different walks

The two versions below differ in exactly one thing: which loop is on the outside. On the left the outer loop picks a row and the inner walks its columns, so you get row sums. On the right the outer loop picks a column and the inner walks its rows, so you get column sums. Both read all nine cells exactly once, and both totals come to 24.

Row-major — one sum per row

for r = 0 to m-1:      // pick a row    sum = 0    for c = 0 to n-1:  // walk it        sum = sum + M[r][c]    rowSum[r] = sum

Column-major — one sum per column

for c = 0 to n-1:      // pick a column    sum = 0    for r = 0 to m-1:  // walk it        sum = sum + M[r][c]    colSum[c] = sum

The outer loop names what you are counting. In the left version sum belongs to a row, so it resets whenever r changes and there are m answers. In the right version it belongs to a column and there are n. If you are summing the wrong thing, the loop order is the bug — not the arithmetic inside.

The visit order changes, the total does not. Row-major reads 4, 1, 3, 2, 5, 0, 6, 2, 1. Column-major reads 4, 2, 6, 1, 5, 2, 3, 0, 1. Nine reads either way, 24 either way, because addition does not care about order. What differs is which subtotals you end up holding: the three row sums 8, 7, 9 on the left against the three column sums 12, 8, 4 on the right. Both triples add to 24.

Row-major is the faster walk on a row-major array. Consecutive cells in the left version are neighbours in memory, so one cache-line fetch serves several reads. The right version jumps n elements per step and can pay a fresh memory fetch on every read. Both are O(m × n) — the difference is wall-clock time on a big matrix, not step count.

Printing a matrix is the same nest with one extra line, and the newline belongs to the outer loop. Print the cell and a space inside the inner loop; print the newline after the inner loop finishes. Put the newline inside and every cell lands on its own line. Leave it out and the whole matrix prints as one long row.

05 Cheat sheet

What gets asked about an m × n matrix

Operation	Cost	Why
Read or write M[r][c]	`O(1)`	One multiply and one add: the address is base + (r × n + c) × size.
Visit every cell	`O(m × n)`	Nothing beats it. There are that many cells and each has to be touched once.
Sum one row	`O(n)`	n cells, and they sit next to each other in memory.
Sum one column	`O(m)`	m cells, each one n elements away from the last.
All row sums (section 03)	`O(m × n)`	The full nest, plus `O(m)` extra space to hold the answers.
Transpose an n × n in place	`O(n²)`	Swap M[r][c] with M[c][r] for every c > r — that is n(n−1)/2 swaps and `O(1)` extra space.

Row-major is the common caseC, C++ and NumPy's default layout store a rectangle as contiguous rows, row 0 first. Fortran, MATLAB and R are column-major. Java's int[][] and a Python list of lists are row-major only in the weaker sense that the first index picks a row — the rows themselves are separate objects, not one block.

The address formulaFor a 0-based row-major array with n columns: base + (r × n + c) × size. Column-major swaps the roles and gives base + (c × m + r) × size. Going back the other way from a flat index k: r = k / n and c = k % n.

Jagged rows break the formulaJava's int[][] is an array of row references, so rows can differ in length and live anywhere on the heap. There is no single n, so the inner loop bound must be the length of that row — not the width of the matrix.

06 Where & why

When a rectangle is the right shape

A 2-D array buys you constant-time access to any cell and the tightest memory layout there is. The price is fixed and paid up front: m × n cells are allocated whether you fill them or not, and the rectangle cannot change shape once it exists.

Reach for one when…

The data really is a rectangleEvery row has the same number of columns, and that number is known when you allocate. Images, game boards, spreadsheets and distance tables all are.

Most cells hold a real valueYou pay for every cell either way, so it only makes sense when most are used. A pixel buffer or a chessboard is dense by definition.

You index by two coordinatesThe question you ask is "give me cell (r, c)", not "give me the neighbours of x". Two numbers in, one value out, in constant time.

You sweep in a fixed orderRow sums, column sums, transposes and DP-table fills all walk the whole grid. A contiguous rectangle makes that sweep as fast as memory allows.

Use something else when…

Situation	Better choice	Why
Rows have different lengths	A jagged array — a list of rows	A rectangle has to be padded out to the widest row, and r × n + c stops being the address of anything.
Almost every cell is zero	A hash map keyed by (r, c), or CSR sparse format	A 10⁵ × 10⁵ matrix is 10¹⁰ cells. You cannot allocate it, and you would be storing zeros in almost all of it.
You are modelling a sparse graph	An adjacency list	An adjacency matrix costs `O(V²)` space, and "list my neighbours" becomes `O(V)` instead of `O(degree)`.
The grid grows while the program runs	A dynamic array of dynamic rows, e.g. vector<vector<int>>	A fixed rectangle has to be reallocated and copied whole to add a single row.

Most matrix interview questions are index-arithmetic questions in a costume. Rotate, transpose, spiral, set-zeroes — none of them need a new data structure. They need you to work out which (r, c) maps to which (r', c'), and then to walk the grid in an order that does not overwrite a cell before you have read it.

07 Interview questions

What they actually ask

Matrix questions turn up in every first round, and half of them are really testing whether you know that M[r][c] is a formula rather than a magic pair of brackets.

What is a 2-D array?

A block of memory holding m × n elements of one type, reached with two indices instead of one. You picture it as a grid of m rows and n columns; the machine stores it as a single flat run of m × n cells. The two-bracket syntax M[r][c] is a convenience the compiler turns into one offset.

What does row-major order mean?

Whole rows are stored one after another: all of row 0, then all of row 1, and so on. So M[r][c] lives at flat position r × n + c, where n is the number of columns. Column-major, which Fortran and MATLAB use, stores full columns instead and gives c × m + r.

Give me the address of M[r][c].

base + (r × n + c) × size, for a 0-based row-major array with n columns. For a 3 × 3 array of 4-byte ints, M[1][2] sits at base + (1×3 + 2)×4 = base + 20. It is one multiply and one add, which is exactly why cell access is O(1) and not a search.

You have a flat index k into a 1-D array. How do you read it as a grid?

r = k / n using integer division and c = k % n. With n = 3 and k = 7 you get r = 2 and c = 1, the middle cell of the last row. This is how you simulate a matrix inside a plain 1-D array, which is what most high-performance libraries actually do.

Row-major and column-major traversal both do m × n reads. Why is one faster?

Cache, not operation count. In a row-major walk the next cell you want is the next cell in memory, so a single cache-line fetch serves several reads. A column-major walk over a row-major array jumps n elements each step and can pay a fresh memory fetch every time. Both are O(m × n); on a large matrix the row-major version can be several times faster in wall-clock.

Which loop should be the outer one?

The one that owns the thing you are producing. For row sums the outer loop walks r, so the running sum is reset once per row and stored once per row. Put that reset in the inner loop and each answer collapses to the last cell of its row; hoist it above the outer loop and the sum never restarts, so you still store m numbers but each is a running total of every row so far — only the last one is the grand total.

What is a jagged array?

A 2-D array whose rows have different lengths. Java’s int[][] is really an array of references to 1-D arrays, so each row is allocated separately and can be any size; a Python list of lists behaves the same way. With jagged rows there is no single n, so the inner loop must run to the length of that specific row.

Is int a[3][4] in C an array of pointers?

No. It is 12 contiguous ints, and a decays to a pointer to an array of 4 ints, not to a pointer to pointers. That is why you must give the column count when you pass it to a function — the compiler needs n to compute r × n + c. Java’s int[][] genuinely is an array of references, and confusing the two is the classic mistake.

How do you sum one column, and what does it cost?

Fix c and loop r from 0 to m−1, adding M[r][c] each time. That is O(m) adds, the same count as summing a row of the same length, but the cells are n apart in memory so the walk is less cache-friendly. On the 3 × 3 in this lesson, column 0 is 4 + 2 + 6 = 12.

How do you transpose a square matrix in place?

Swap M[r][c] with M[c][r] for every pair where c > r. Starting the inner loop at c = r + 1 is the whole trick: start it at 0 and you swap each pair twice, which puts the matrix back exactly as it was. An n × n transpose is n(n−1)/2 swaps and O(1) extra space; a non-square matrix cannot be done in place because the result has different dimensions.

Rotate a matrix 90 degrees clockwise — how?

Hard

If any cell of an m × n matrix is 0, set that cell’s whole row and whole column to 0. Use no extra array — only a constant number of variables.

Follow-up

A single pass corrupts its own input: the zeros you write become zeros you later read as if they were original. The fix is to store your marks inside the matrix itself, which then makes the first row and first column ambiguous.

Show the hint

Use row 0 and column 0 as the marker storage, plus two separate flags recording whether row 0 and column 0 each held a zero to begin with. Fill the interior first, then those two edges last.