How column-major traversal works
Picture a spreadsheet where you need the total of every column. You would not read it line by line. You would run your finger down column A, write the total, then down column B, and so on. That is column-major order: finish one whole column before moving one step to the right.
The surprising part is how little changes in the code. Take the two nested loops of row-major traversal and swap them: the outer loop now picks a column j, the inner loop walks the rows i. Inside, you still read a[i][j], row first, column second. Only the order of the loops moved.
Watch the headers in the visualizer: the column header stays lit while the row header runs down, exactly the opposite of the row-major page.
The loop shape
Outer loop: j from 0 to cols − 1. Inner loop: i from 0 to rows − 1. The inner index is now the row, so i changes on every step and j only when a column is used up.
A common trap: people swap the loops and swap the indices inside, writing a[j][i]. That undoes the change on a square grid and crashes on a rectangular one. Swap the loops, keep the access.
A worked example: a 3 × 4 grid
With the cells numbered 1 to 12 in reading order, column-major order picks every fourth number, then starts again one place to the right:
Column 0 gives 1, 5, 9; column 1 gives 2, 6, 10; and so on. Four columns of three cells is still 12 steps. The total work is the same as row-major, only the order differs.
Where you'll meet it
- Column totals and column checks. Sudoku columns, the sum of each column of a table, the maximum in each column of a chart.
- Transposing. Reading a grid column by column and writing row by row is a transpose.
- Fortran, MATLAB, R and Julia. Their arrays are stored this way, so their fast loops go down columns, the reverse of C and Python.
- NumPy.
np.array(x, order="F")lays the data out column-major to match those libraries.
Mistakes beginners make
- Swapping the access too. The loops swap;
a[i][j]does not. - Taking the column count from the wrong place. The number of columns is
a[0].length, the length of one row, nota.length. - Expecting it to be as fast. On a row-major array, a large grid walked column by column can be several times slower. If speed matters, match the storage order.
Both orders jump back to the start of each line. Next, a path that never jumps: Snake traversal →
Column-major questions
What is the difference between row-major and column-major order?
Row-major walks across one row at a time, so the column index changes fastest. Column-major walks down one column at a time, so the row index changes fastest. In code it is the same two loops with the outer and inner loop swapped.
Which languages use column-major order?
Fortran, MATLAB, R and Julia store 2D arrays column by column. NumPy can do either: the default is row-major (order="C"), and order="F" gives column-major. Knowing which one your data uses tells you which loop order will be fast.
Is column-major traversal slower?
It depends on how the grid is stored, not on the traversal itself. Walking down a column of a row-major array jumps through memory and wastes cache; walking down a column of a column-major array is a straight line. The loop that matches the storage order wins.
When would I choose column-major traversal on purpose?
Whenever the question is about columns: the total of each column, the tallest bar in each column of a chart, or checking every column of a puzzle grid for a repeated value. The inner loop then finishes one column before the outer loop moves on.