Pattern #12

Matrix Traversal

Important interview questions, thinking patterns, 4-direction tricks, and rules for solving matrix traversal problems in Go.

Must Solve

16 core questions — solve these first.

1.Spiral Matrix
4 boundaries (top, bottom, left, right)medium
2.Rotate Image
Transpose + Reverse Rows in-placemedium
3.Set Matrix Zeroes
Use 1st row/col as markersmedium
4.Search a 2D Matrix
Treat 2D as 1D array (Binary Search)medium
5.Search a 2D Matrix II
Start from top-right cornermedium
6.Diagonal Traverse
Flip direction on boundarymedium
7.Reshape the Matrix
1D flat index r*C+c to r2/c2easy
8.Transpose Matrix
Swap matrix[i][j] with matrix[j][i]easy
9.Valid Sudoku
Row, Col, 3x3 Box HashSetsmedium
10.Game of Life
In-place state encoding bitsmedium
11.Flood Fill
Grid DFS / BFS color filleasy
12.Number of Islands
Grid DFS / BFS connected componentsmedium
13.Surrounded Regions
DFS from border O to saved statemedium
14.Word Search
Grid Backtracking DFSmedium
15.Max Area of Island
Grid DFS area countmedium
16.Pacific Atlantic Water Flow
BFS/DFS backwards from oceansmedium

Also Important

10 more questions worth practicing.

17.Matrix Diagonal Sum
Sum main & anti-diagonalseasy
18.Toeplitz Matrix
Check matrix[i][j] == matrix[i-1][j-1]easy
19.Richest Customer Wealth
Row sum maxeasy
20.Count Negative Numbers in a Sorted Matrix
Start from bottom-left cornereasy
21.Lucky Numbers in a Matrix
Min in row & max in coleasy
22.Rotate the Box
Rotate 90° + Gravity Simulationmedium
23.Spiral Matrix II
Fill 1..n^2 with 4 boundariesmedium
24.Battleships in a Board
Count top-left corner of shipsmedium
25.Number of Closed Islands
Flood fill border islands firstmedium
26.Shortest Path in Binary Matrix
8-directional Grid BFSmedium

How to Think

Need visit every cell?Rows × Columns → O(rows × cols)
Need four directions?dirs := [][]int{{-1,0},{1,0},{0,-1},{0,1}}
Need spiral?top, bottom, left, right (shrink boundaries)
Need rotate matrix 90°?Transpose + Reverse Rows
Need connected cells / islands?Grid DFS / BFS
Need search sorted matrix?Binary Search or Top-Right Corner

Go Templates

Basic Nested Matrix Traversal

rows, cols := len(matrix), len(matrix[0])
for r := 0; r < rows; r++ {
    for c := 0; c < cols; c++ {
        val := matrix[r][c] // Choose row first, then column
        _ = val
    }
}

4-Directional Traversal Loop

dirs := [][]int{
    {-1, 0}, // Up
    {1, 0},  // Down
    {0, -1}, // Left
    {0, 1},  // Right
}

for _, d := range dirs {
    nr, nc := row+d[0], col+d[1]
    if nr >= 0 && nr < rows && nc >= 0 && nc < cols {
        // Valid neighboring cell inside bounds!
    }
}

Main Direction Trick & Rotate Transformation

Instead of writing 4 separate if-statements for Up, Down, Left, Right, use a direction array dirs:

dirs := [][]int{ {-1,0}, {1,0}, {0,-1}, {0,1} }

Rotate Matrix 90° Clockwise In-Place

1. Transpose: Swap matrix[i][j] with matrix[j][i]
2. Reverse Each Row: Reverse values in each row

Result: 90° Clockwise Rotation ✅

Visual Memory Rule

Spiral:  → top  ↓ right  ← bottom  ↑ left  (shrink boundaries)
Rotate:  Transpose + Reverse Rows
Dirs:    (-1,0), (1,0), (0,-1), (0,1)

💡 Golden Rule: "In matrix problems, always know: where am I, which direction can I move, and is the next cell valid?"

Common Interview Mistakes

1. Row / Column Confusion

Accidentally writing matrix[col][row] instead of matrix[row][col].

2. Out of Bounds Check Order

Check 0 <= nr < rows && 0 <= nc < cols BEFORE accessing matrix[nr][nc].

3. Infinite DFS Cycles

Forgetting a visited[r][c] set or mutating visited cells causes infinite recursion.

4. Assuming Square Matrix

Matrices can be non-square 3 x 5. Always use rows = len(matrix) and cols = len(matrix[0]).

Interview Rules

1. Visit every cell? → Rows × Columns
2. Four-direction movement? → Direction array dirs
3. Connected cells / Islands? → Grid DFS/BFS
4. Spiral? → 4 boundaries (top, bottom, left, right)
5. Rotate 90° clockwise? → Transpose + Reverse Rows
6. Sorted matrix? → Binary Search / Start from Top-Right corner
7. Avoid repeating visits? → Use visited matrix/set
8. Always check bounds before array lookup
9. Time complexity → usually O(rows × cols)
10. Don't assume square matrix (rows != cols)

Small Rules

Rule 1: Always know both rows = len(matrix) and cols = len(matrix[0]).
Rule 2: Check 0 <= newRow < rows && 0 <= newCol < cols before accessing cell.
Rule 3: Nested loops over matrix are normal O(rows × cols), not bad complexity.
Rule 4: Avoid visiting cells twice in grid DFS/BFS using a visited tracking mechanism.
Rule 5: Be careful with non-square matrices where rows != cols.

Production Thinking

Image Processing → Pixels matrix (crop, rotate 90°, blur, edge detection)

Maps & Gaming Grids → Grid BFS/DFS for pathfinding (0=free, 1=blocked)

Spreadsheet Processing → Row x Column cell traversal & region aggregations

Seat Booking Systems → Cinema/Airplane seat layout matrix (adjacent seat availability)

Game Boards → Chess, Sudoku, Tic-Tac-Toe board state validation

Remember This

Every cell          → rows × cols
Neighbors           → direction array
Connected region    → DFS / BFS
Spiral              → top, right, bottom, left
Rotate 90°          → transpose + reverse
Sorted matrix       → binary search / corner search
Before moving       → bounds check
Visited before?     → skip

💡 Golden Rule: "In matrix problems, always know: where am I, which direction can I move, and is the next cell valid?"