Skills101

AdvancedData Structures & Algorithms · Lesson 21 of 25 · Updated ·

Matrix Traversal — Rows, Columns, Spiral, Diagonals and Grid Moves

A matrix (2D array) is a grid of R rows and C columns; m[r][c] is the cell in row r, column c. Matrix questions are everywhere in placement tests — spiral print, rotate image, search a sorted matrix, count islands — and they all come down to visiting cells in a particular order without going out of bounds.

1. Row by row and column by column

m = [[1, 2, 3],
     [4, 5, 6]]
R, C = len(m), len(m[0])

for r in range(R):                      # row-major: the normal reading order
    print(*[m[r][c] for c in range(C)])

cols = [[m[r][c] for r in range(R)] for c in range(C)]   # column-major
print(cols)
print([sum(row) for row in m], [sum(col) for col in cols])
1 2 3
4 5 6
[[1, 4], [2, 5], [3, 6]]
[6, 15] [5, 7, 9]
  • R = len(m) is the number of rows; C = len(m[0]) the number of columns.
  • Visiting every cell is always O(R × C).

2. Spiral order

Print the matrix going right → down → left → up, then move inward. Keep four borders — top, bottom, left, right — and shrink one after each side is printed.

A 4 by 4 matrix numbered 1 to 16 traversed in spiral order: 1 2 3 4 8 12 16 15 14 13 9 5 then the inner ring 6 7 11 10; arrows show right, down, left, up and then the inner ring

def spiral(m):
    out = []
    top, bottom, left, right = 0, len(m) - 1, 0, len(m[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1): out.append(m[top][c])
        top += 1
        for r in range(top, bottom + 1): out.append(m[r][right])
        right -= 1
        if top <= bottom:                         # a row is still left
            for c in range(right, left - 1, -1): out.append(m[bottom][c])
            bottom -= 1
        if left <= right:                         # a column is still left
            for r in range(bottom, top - 1, -1): out.append(m[r][left])
            left += 1
    return out

print(spiral([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]))
print(spiral([[1, 2, 3], [4, 5, 6]]))
[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]
[1, 2, 3, 6, 5, 4]

The two if checks matter for non-square matrices: without them, a single remaining row or column gets printed twice.

3. Transpose and rotate by 90°

Transpose swaps rows and columns: t[c][r] = m[r][c]. Rotating a square matrix 90° clockwise in place = transpose, then reverse every row.

def rotate_clockwise(m):
    n = len(m)
    for r in range(n):
        for c in range(r + 1, n):                 # only above the diagonal
            m[r][c], m[c][r] = m[c][r], m[r][c]
    for row in m:
        row.reverse()
    return m

for row in rotate_clockwise([[1, 2, 3], [4, 5, 6], [7, 8, 9]]):
    print(row)
[7, 4, 1]
[8, 5, 2]
[9, 6, 3]
  • The inner loop starts at r + 1; starting at 0 would swap every pair twice and undo the transpose.
  • Anticlockwise: transpose, then reverse every column (or reverse the rows first, then transpose).

4. Diagonals

Cells on the same main diagonal have the same r − c; cells on the same anti-diagonal have the same r + c. That one fact solves diagonal sums, "is this a valid N-Queens board" and "print the matrix diagonally".

m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
n = len(m)
print(sum(m[i][i] for i in range(n)), sum(m[i][n - 1 - i] for i in range(n)))

diag = {}
for r in range(n):
    for c in range(n):
        diag.setdefault(r + c, []).append(m[r][c])
print([diag[k] for k in sorted(diag)])
15 15
[[1], [2, 4], [3, 5, 7], [6, 8], [9]]

5. Moving to neighbours: direction arrays

Grid problems (islands, flood fill, shortest path in a maze, rotting oranges) move from a cell to its 4 neighbours. Write the moves once as two arrays instead of four copies of the same code.

A 3 by 3 grid with the centre cell (r,c) and its four neighbours r-1, r+1, c-1 and c+1, next to the code dr = [-1, 1, 0, 0], dc = [0, 0, -1, 1] and a bounds check before reading the neighbour

Here is a breadth-first search that counts the steps from the top-left to the bottom-right corner of a maze (# = wall):

from collections import deque

def shortest_path(grid):
    R, C = len(grid), len(grid[0])
    dist = [[-1] * C for _ in range(R)]
    dist[0][0] = 0
    q = deque([(0, 0)])
    while q:
        r, c = q.popleft()
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == '.' and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist[R - 1][C - 1]

maze = ["..#.",
        ".##.",
        "....",
        "#.#."]
print(shortest_path(maze))
6

For 8 directions (king moves, "count neighbours" in Game of Life), add the four diagonal moves (±1, ±1).

The same spiral in Java

import java.util.*;

public class Main {
    static List<Integer> spiral(int[][] m) {
        List<Integer> out = new ArrayList<>();
        int top = 0, bottom = m.length - 1, left = 0, right = m[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) out.add(m[top][c]);
            top++;
            for (int r = top; r <= bottom; r++) out.add(m[r][right]);
            right--;
            if (top <= bottom) { for (int c = right; c >= left; c--) out.add(m[bottom][c]); bottom--; }
            if (left <= right) { for (int r = bottom; r >= top; r--) out.add(m[r][left]); left++; }
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(spiral(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}));
    }
}
[1, 2, 3, 6, 9, 8, 7, 4, 5]

Common mistakes

  • Mixing up R and C on a non-square matrix (len(m) is rows, len(m[0]) is columns).
  • Creating a grid with [[0] * C] * R in Python — every row is the same list, so changing one row changes all of them. Use [[0] * C for _ in range(R)].
  • Reading grid[nr][nc] before checking 0 ≤ nr < R and 0 ≤ nc < C.
  • In spiral order, forgetting the two if checks, which repeats the middle row or column.

Quick recap

  • Every full traversal is O(R × C); the question is only the order.
  • Spiral: four shrinking borders, with checks for the last row/column.
  • Rotate 90° clockwise = transpose + reverse each row.
  • Same diagonal: equal r − c; same anti-diagonal: equal r + c.
  • Neighbours: direction arrays plus a bounds check; BFS on a grid gives shortest paths.

Practice what you learned

📝 Quiz: Matrix Traversal5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →