Matrix Traversal
Matrix traversal means visiting the cells of a 2D grid in a planned order, most often row by row using two indexes, i for the row and j for the column. Interviewers like it because it is simple to state but easy to get wrong: off-by-one bounds, mixing up rows and columns, and handling empty or non-square grids all show up quickly. Once you are comfortable with the basic loop, the same ideas extend to spirals, diagonals, and neighbor checks.
When to use it
- The input is a 2D array, grid, board, or matrix of numbers or characters.
- You must visit, count, sum, or transform every cell (or every cell in a special order like a spiral or diagonal).
- The answer depends on a cell's neighbors: up, down, left, right (or all 8 directions).
- The problem asks to rotate, transpose, flip, or print the matrix in a certain order.
- Rows and columns are given as m x n and you need to be careful about boundaries.
See it work
- Take a 3x3 grid. We want to visit every cell row by row and add up the values. Start at row i = 0, column j = 0. The first cell is grid[0][0] = 1, so the running sum is 1.
[1, 2, 3, 4, 5, 6, 7, 8, 9] - Move j to the right across row 0: j = 1 gives 2, j = 2 gives 3. The running sum is 1 + 2 + 3 = 6. When j reaches the number of columns (3), the inner loop ends.
[1, 2, 3, 4, 5, 6, 7, 8, 9] - Now i becomes 1 and j resets to 0. We read grid[1][0] = 4, then 5, then 6. Each cell's flat position is i * 3 + j, so (1,0) is position 3. The sum grows to 6 + 15 = 21.
[1, 2, 3, 4, 5, 6, 7, 8, 9] - Last row: i = 2. Visit 7, 8, 9 at positions 6, 7, 8. The sum becomes 21 + 24 = 45. When i reaches the number of rows (3), the outer loop ends.
[1, 2, 3, 4, 5, 6, 7, 8, 9] - To look at neighbors, use direction offsets. From the center cell (1,1) = 5, the four neighbors are (0,1), (2,1), (1,0), (1,2). Before reading each one, check 0 <= ni < rows and 0 <= nj < cols. The neighbors are 2, 8, 4, 6.
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Code template
Python
def traverse(grid):
if not grid or not grid[0]:
return
rows, cols = len(grid), len(grid[0])
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] # up, down, left, right
for i in range(rows): # row by row
for j in range(cols): # left to right
value = grid[i][j] # process the cell here
for di, dj in dirs: # optional: look at neighbors
ni, nj = i + di, j + dj
if 0 <= ni < rows and 0 <= nj < cols:
neighbor = grid[ni][nj] # safe to useC
void traverse(int rows, int cols, int grid[rows][cols]) {
if (rows == 0 || cols == 0) return;
int di[4] = {-1, 1, 0, 0}; /* up, down, left, right */
int dj[4] = {0, 0, -1, 1};
for (int i = 0; i < rows; i++) { /* row by row */
for (int j = 0; j < cols; j++) { /* left to right */
int value = grid[i][j]; /* process the cell here */
(void)value;
for (int d = 0; d < 4; d++) { /* optional: look at neighbors */
int ni = i + di[d], nj = j + dj[d];
if (ni >= 0 && ni < rows && nj >= 0 && nj < cols) {
int neighbor = grid[ni][nj]; /* safe to use */
(void)neighbor;
}
}
}
}
}Java
void traverse(int[][] grid) {
if (grid.length == 0 || grid[0].length == 0) return;
int rows = grid.length, cols = grid[0].length;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // up, down, left, right
for (int i = 0; i < rows; i++) { // row by row
for (int j = 0; j < cols; j++) { // left to right
int value = grid[i][j]; // process the cell here
for (int[] d : dirs) { // optional: look at neighbors
int ni = i + d[0], nj = j + d[1];
if (ni >= 0 && ni < rows && nj >= 0 && nj < cols) {
int neighbor = grid[ni][nj]; // safe to use
}
}
}
}
}
Complexity: Time is O(m * n) because each of the m x n cells is visited a constant number of times; extra space is O(1) for a plain traversal (more if you build an output or visited grid).
Programs that use it
Interview problems that use it
- Spiral Matrix: Keep four shrinking boundaries (top, bottom, left, right) and walk the edge of the remaining rectangle, then move each boundary inward.
- Rotate Image (90 degrees in place): Transpose the matrix by swapping grid[i][j] with grid[j][i], then reverse each row.
- Diagonal Traverse: Cells on the same diagonal share the same i + j, so walk each diagonal and flip the direction every other time.
- Set Matrix Zeroes: Scan the grid to record which rows and columns contain a zero, then do a second pass that zeroes those rows and columns.
- Number of Islands: Scan every cell; when you find an unvisited land cell, count one island and flood-fill its neighbors so they are not counted again.
- Search a 2D Matrix: Start at the top-right corner and move left when the value is too big or down when it is too small, since rows and columns are sorted.
Common mistakes
- Swapping rows and columns: rows is len(grid) and cols is len(grid[0]). Looping j up to rows on a non-square grid causes index errors or skipped cells.
- Forgetting the bounds check on neighbors, so grid[i-1][j] at i = 0 silently wraps around in Python (negative index) or crashes in other languages.
- Not handling an empty grid or an empty first row before reading grid[0], and modifying the grid while scanning it so later cells see already-changed values.
Frequently asked questions
How do I loop through a 2D array by rows and columns?
Use a nested loop: the outer loop runs i from 0 to rows - 1, the inner loop runs j from 0 to cols - 1, and you read grid[i][j]. Get rows from len(grid) and cols from len(grid[0]).
What is a direction array and why use it?
It is a small list of (row change, column change) pairs such as (-1,0), (1,0), (0,-1), (0,1). Looping over it lets you visit up, down, left, and right neighbors without writing four copies of the same code.
Is row-by-row traversal faster than column-by-column?
Both are O(m * n), but row by row is usually faster in practice for languages like C and Java, where each row is stored contiguously in memory and so is friendlier to the CPU cache.