2.21 Matrix Traversal

Matrix traversal processes a two-dimensional array in a defined order. It is the two-dimensional form of array traversal, but the extra dimension adds boundary choices, coordinate conventions, and common patterns such as row-major order, column-major order, diagonal scans, and grid-neighbor exploration.

Problem

Given a matrix a with rows rows and cols columns, visit every cell exactly once.

Example:

1 2 3
4 5 6
7 8 9

A row-major traversal visits:

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

A column-major traversal visits:

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

Row-Major Traversal

Row-major traversal scans each row from left to right.

func TraverseRowMajor(a [][]int, visit func(int, int, int)) {
	for r := 0; r < len(a); r++ {
		for c := 0; c < len(a[r]); c++ {
			visit(r, c, a[r][c])
		}
	}
}

Invariant:

Before processing a[r][c], all cells in earlier rows and all cells before c in row r have already been processed.

This is the natural traversal for Go slices because each row is itself a slice.

Rectangular Matrix Traversal

If the matrix is guaranteed rectangular, compute dimensions once.

func TraverseRect(a [][]int, visit func(int, int, int)) {
	rows := len(a)
	if rows == 0 {
		return
	}

	cols := len(a[0])

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			visit(r, c, a[r][c])
		}
	}
}

Precondition:

Every row has length cols.

Without this precondition, a[r][c] may panic on ragged input.

Column-Major Traversal

Column-major traversal scans one column at a time.

func TraverseColumnMajor(a [][]int, visit func(int, int, int)) {
	rows := len(a)
	if rows == 0 {
		return
	}

	cols := len(a[0])

	for c := 0; c < cols; c++ {
		for r := 0; r < rows; r++ {
			visit(r, c, a[r][c])
		}
	}
}

For row-based storage, column-major traversal can have worse cache locality because consecutive accesses may jump between different row slices.

Flattened Index

A rectangular matrix can be mapped to one linear index.

index = r * cols + c
r = index / cols
c = index % cols

func TraverseFlat(a [][]int, visit func(int, int, int)) {
	rows := len(a)
	if rows == 0 {
		return
	}

	cols := len(a[0])
	total := rows * cols

	for i := 0; i < total; i++ {
		r := i / cols
		c := i % cols
		visit(r, c, a[r][c])
	}
}

This form is useful when a grid must be treated as a graph or when work is distributed by linear ranges.

Reverse Traversal

Reverse row-major order scans from bottom-right to top-left.

func TraverseReverse(a [][]int, visit func(int, int, int)) {
	for r := len(a) - 1; r >= 0; r-- {
		for c := len(a[r]) - 1; c >= 0; c-- {
			visit(r, c, a[r][c])
		}
	}
}

For unsigned indices, reverse loops require extra care. In Go, use signed int indices as above.

Diagonal Traversal

Cells on the same diagonal have constant r + c.

func TraverseDiagonals(a [][]int, visit func(int, int, int)) {
	rows := len(a)
	if rows == 0 {
		return
	}

	cols := len(a[0])

	for sum := 0; sum <= rows+cols-2; sum++ {
		for r := 0; r < rows; r++ {
			c := sum - r
			if 0 <= c && c < cols {
				visit(r, c, a[r][c])
			}
		}
	}
}

Invariant:

During outer iteration sum, only cells with r + c = sum are visited.

This pattern appears in dynamic programming when a state depends on smaller diagonals.

Anti-Diagonal Traversal

Cells on the same anti-diagonal have constant r - c.

A practical way to scan anti-diagonals is to start from the first row and first column.

func TraverseAntiDiagonals(a [][]int, visit func(int, int, int)) {
	rows := len(a)
	if rows == 0 {
		return
	}

	cols := len(a[0])

	for startC := 0; startC < cols; startC++ {
		r, c := 0, startC
		for r < rows && c >= 0 {
			visit(r, c, a[r][c])
			r++
			c--
		}
	}

	for startR := 1; startR < rows; startR++ {
		r, c := startR, cols-1
		for r < rows && c >= 0 {
			visit(r, c, a[r][c])
			r++
			c--
		}
	}
}

Neighbor Traversal

Grid algorithms often treat each cell as a graph vertex.

Four-neighbor movement:

up, down, left, right

var dirs4 = [][2]int{
	{-1, 0},
	{1, 0},
	{0, -1},
	{0, 1},
}

func ForEachNeighbor4(rows, cols, r, c int, visit func(int, int)) {
	for _, d := range dirs4 {
		nr := r + d[0]
		nc := c + d[1]

		if 0 <= nr && nr < rows && 0 <= nc && nc < cols {
			visit(nr, nc)
		}
	}
}

Eight-neighbor movement includes diagonals.

var dirs8 = [][2]int{
	{-1, -1}, {-1, 0}, {-1, 1},
	{0, -1},           {0, 1},
	{1, -1},  {1, 0},  {1, 1},
}

Boundary Checks

Use a helper when boundary checks appear many times.

func InBounds(rows, cols, r, c int) bool {
	return 0 <= r && r < rows && 0 <= c && c < cols
}

This reduces repeated logic and avoids inconsistent bounds.

Complexity

For a rectangular matrix:

Time:  O(rows * cols)
Space: O(1)

Neighbor traversal over all cells is also linear if each cell checks a constant number of neighbors.

Common Pitfalls

Assuming a ragged matrix is rectangular can cause out-of-range access.

Confusing rows and cols is common in neighbor checks.

Reverse loops can underflow when unsigned indices are used.

Column-major traversal may be slower on row-oriented storage.

Diagonal traversal often has off-by-one errors in the outer loop bound.

Using (r, c) inconsistently as (x, y) leads to incorrect movement logic.

Takeaway

Matrix traversal is controlled iteration over coordinates. Choose an order that matches the dependency structure of the algorithm: row-major for ordinary scans, diagonal order for diagonal dynamic programming, and neighbor traversal for grid graphs. Keep coordinate conventions explicit and centralize boundary checks.