# 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:

```text id="5s9t2w"
1 2 3
4 5 6
7 8 9
```

A row-major traversal visits:

```text id="l8q1va"
1, 2, 3, 4, 5, 6, 7, 8, 9
```

A column-major traversal visits:

```text id="p4e6wn"
1, 4, 7, 2, 5, 8, 3, 6, 9
```

## Row-Major Traversal

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

```go id="fw7s3m"
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:

```text id="u2rz8k"
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.

```go id="hd6n0r"
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:

```text id="zgsh8w"
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.

```go id="w4yfmt"
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.

```text id="c0d7wn"
index = r * cols + c
r = index / cols
c = index % cols
```

```go id="cklm26"
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.

```go id="ulr71v"
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`.

```go id="m8kiyd"
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:

```text id="hbvcas"
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.

```go id="es0opm"
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:

```text id="th7p5x"
up, down, left, right
```

```go id="h5hm2l"
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.

```go id="rn75gf"
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.

```go id="y9ev3t"
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:

```text id="h51bei"
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.