Row-Major Traversal of a Matrix

Row-Major Traversal of a Matrix

A matrix is just a table of numbers. It has rows (going across, left to right) and columns (going down, top to bottom). In code, we often store a matrix as a list of lists, where each inner list is one row.

For example:

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

This matrix has 3 rows and 3 columns.

What does "traversal" mean?

To traverse a matrix means to visit every single number in it, one by one, in some order. The order we pick has a name. Here we use row-major order.

What is row-major order?

In row-major order, we read the numbers one full row at a time, from top to bottom. Think of it exactly like reading a page in a book: you read the first line completely from left to right, then drop down to the next line and read it completely, and so on.

So for the matrix above, we read:

• First the top row: 1, 2, 3
• Then the middle row: 4, 5, 6
• Then the bottom row: 7, 8, 9

Joined together, the output is:

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

The key idea to remember: *the consecutive elements of a single row sit next to each other in the result.* We finish a whole row before moving to the next one.

Another example

Rows do not have to be the same length as the number of rows. Take this matrix with 2 rows and 4 columns:

matrix = [[3, 2, 1, 7],
          [0, 6, 3, 2]]

Read the first row fully (3, 2, 1, 7), then the second row fully (0, 6, 3, 2). The output is:

[3, 2, 1, 7, 0, 6, 3, 2]

How to do it in code

The natural way is to use two loops, one inside the other:

1. The outer loop picks a row, starting from row 0 and going down to the last row.
2. The inner loop walks across that chosen row, from the first column to the last, and copies each number into the result list.

In C++ the function header looks like this:

class Solution {
public:
    vector<int> rowMajorTraversal(vector<vector<int>>& matrix) {
    }
};

Here matrix[i][j] means: the number at row i and column j. The outer loop changes i (which row), and the inner loop changes j (which column). You append matrix[i][j] to your answer each time, and when both loops finish, you return the answer.

The result simply follows the reading order: across each row, then down to the next.