Column-Major Traversal of a Matrix

Column-Major Traversal of a Matrix

A matrix is just a table of numbers arranged in rows and columns. Think of it like a chessboard or a spreadsheet, where every box holds one value. To work with a matrix, we often need to visit every box one by one. The order in which we visit them is called a traversal.

There are two common ways to walk through a matrix. The usual way is row by row — finish the whole first row, then the second row, and so on. But here we learn a different order: column-major traversal, where we go column by column instead.

What "column-major" means

In column-major order, we visit all the numbers in the first column from top to bottom, then move to the second column and read it top to bottom, and keep going until every column is done. In simple words: the numbers of one full column stay together, one after another, before we touch the next column.

A worked example

Take this matrix:

matrix = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]

Here the columns are:

• Column 0 (the leftmost) holds 1, 4, 7 (top to bottom).
• Column 1 (the middle) holds 2, 5, 8.
• Column 2 (the rightmost) holds 3, 6, 9.

So we read column 0 first → 1, 4, 7, then column 1 → 2, 5, 8, then column 2 → 3, 6, 9. Joining them gives the answer:

Output: [1, 4, 7, 2, 5, 8, 3, 6, 9]

Notice how 1, 4, 7 are the top, middle, and bottom of the same column. That is the key idea — we move down a column before moving right to the next one.

How to think about the loops

To pick a value we use two index numbers: a row index and a column index, written as matrix[row][col]. In a normal row-major walk, the outer loop runs over rows and the inner loop over columns. For column-major, we simply swap that order:

1. The outer loop picks a column, starting at column 0.
2. The inner loop moves down every row of that column, reading matrix[row][col] from top to bottom.
3. Add each value to the answer list as you read it.
4. When one column is finished, the outer loop moves to the next column and repeats.

In C++ this fits a function like:

vector<int> columnMajorTraversal(vector<vector<int>> matrix)

It takes the matrix and returns a list (vector<int>) holding the numbers in column-major order.

One more example

For matrix = [[3, 2, 1, 7], [0, 6, 3, 2]], there are 2 rows and 4 columns. Reading each column top to bottom gives: column 0 → 3, 0; column 1 → 2, 6; column 2 → 1, 3; column 3 → 7, 2. So the traversal is [3, 0, 2, 6, 1, 3, 7, 2].

The single thing to remember: down a column first, then across to the next column.