Matrix Traversal and Operations

2D matrices appear in grid, image, and dynamic-programming problems. Interviews test index arithmetic (row/column mapping), in-place transformations, and non-linear traversal orders like spiral and diagonal.

The core idea

An m×n matrix is just rows of arrays; element (r, c) is reached in O(1). Key operations:

• Rotate 90° clockwise in place: transpose (swap a[i][j] with a[j][i]) then reverse each row → O(m·n) time, O(1) space.
• Spiral traversal: maintain top/bottom/left/right boundaries and shrink them after each edge → O(m·n).
• Set matrix zeroes: use the first row/column as marker storage to hit O(1) extra space.
• Search a sorted matrix: start at the top-right corner and move left or down → O(m+n).

Operation	Time	Space
Element access (r,c)	O(1)	O(1)
Full traversal	O(m·n)	O(1)
Rotate 90° in place	O(m·n)	O(1)
Spiral order	O(m·n)	O(1)
Search row+col sorted	O(m+n)	O(1)

Exam Tricks & Tips

• 🎯 Rotate 90° clockwise = transpose + reverse each row; anticlockwise = transpose + reverse each column.
• 🎯 Sorted-both-ways matrix search: start top-right — larger ⇒ go down, smaller ⇒ go left, O(m+n).
• 🎯 Set-zeroes in O(1) space: use row 0 and col 0 as flags, handling their own zero separately first.
• 🎯 Map a 2D index to 1D as r·numCols + c, and back with divide/modulo — useful for flattening.
• 🎯 Spiral: process a full boundary layer, then move all four bounds inward by one.
• ❌ Common mistake: confusing m (rows) and n (columns) in loop bounds on a non-square matrix.

Expected pattern

Rotate an image, spiral/diagonal print, set zeroes, search a sorted matrix, or flood-fill/island counting on a grid. Interviewers check clean boundary handling and correct in-place transforms.

Quick recap

Matrix = rows of arrays, O(1) access, O(m·n) traversal. Rotate via transpose + row-reverse in place; spiral via four shrinking boundaries; search a sorted matrix from the top-right in O(m+n). Watch rows-vs-columns on non-square grids.

Cover the answer, recall, then check. 11 cards on matrix traversal and operations.

Q1. Rotate a matrix 90° clockwise in place — steps?
A1. Transpose (swap a[i][j] with a[j][i]), then reverse each row. O(m·n) time, O(1) space.

Q2. Rotate 90° anticlockwise in place?
A2. Transpose, then reverse each column (or reverse rows first, then transpose).

Q3. Search a row- and column-sorted matrix efficiently?
A3. Start at the top-right: if target is smaller go left, if larger go down. O(m+n).

Q4. Traverse a matrix in spiral order — approach?
A4. Keep top/bottom/left/right bounds; walk each edge, then shrink the bound inward. O(m·n).

Q5. Set matrix zeroes in O(1) extra space?
A5. Use the first row and column as markers; record their own zero state in two flags handled separately.

Q6. Map 2D index (r, c) to a 1D index?
A6. index = r × numCols + c; reverse with r = index / numCols, c = index % numCols.

Q7. Complexity to visit every cell once?
A7. O(m·n) time; O(1) extra space with no auxiliary structure.

Q8. Common bug on non-square matrices?
A8. Swapping the roles of m (rows) and n (columns) in loop bounds or index math.

Q9. Number-of-islands traversal technique?
A9. DFS or BFS flood-fill from each unvisited land cell; O(m·n) total.

Q10. Why does top-right search work but top-left doesn't?
A10. From top-right one direction increases and the other decreases values, giving a clean decision; top-left is ambiguous.

Q11. Diagonal traversal index insight?
A11. Cells on the same diagonal share a constant r + c (or r − c), letting you group them in O(m·n).

A matrix is a 2-D array, and interviewers use it to test index discipline: rotating in place, spiral traversal, transposing, and searching a sorted grid. Master the coordinate bookkeeping and these become mechanical.

Core idea: an m×n matrix is stored as rows of contiguous elements; M[r][c] is O(1) access. Most matrix problems are careful bounded loops over (row, col) pairs, so the whole art is managing boundaries without going out of range.

How it works

Beginner — traversal and transpose

A full traversal visits m·n cells → O(m·n) time. The transpose swaps M[r][c] with M[c][r]; done in place on a square matrix it needs only the cells above the diagonal:

for r in 0..n-1:
    for c in r+1..n-1:
        swap(M[r][c], M[c][r])

O(n²) time, O(1) space.

Intermediate — rotate 90° in place

Rotating a square matrix clockwise = transpose, then reverse each row:

transpose(M)
for each row: reverse(row)

Both steps are O(n²) time with O(1) extra space. (Anticlockwise = transpose then reverse each column, or reverse rows first then transpose.)

Advanced — spiral traversal and sorted-grid search

Spiral order walks the outer ring, then shrinks the boundary. Keep four bounds top, bottom, left, right; after traversing each edge, move that boundary inward and check top <= bottom && left <= right before the next edge. O(m·n) time.

Search a row-and-column-sorted matrix (each row ascends, each column ascends): start at the top-right corner. If the target is smaller, move left; if larger, move down. Each step eliminates a full row or column → O(m + n) time, far better than O(m·n) scanning or even O(m log n) per-row binary search.

Worked example

Rotate [[1,2,3],[4,5,6],[7,8,9]] 90° clockwise.
Transpose → [[1,4,7],[2,5,8],[3,6,9]]. Reverse each row → [[7,4,1],[8,5,2],[9,6,3]]. That is exactly the input rotated a quarter-turn clockwise, with no second matrix allocated.

When to use it

• Transpose/rotate: image rotation, "rotate the matrix in place".
• Spiral: print/collect elements in spiral order, generate a spiral matrix.
• Top-right staircase search: "search a sorted 2-D matrix", "find in Young tableau".
• BFS/DFS over a grid: islands, flood fill, shortest path in a maze (covered under Graphs).

Tricks & gotchas

• Distinguish row-count m from column-count n; mixing them causes out-of-bounds on non-square grids.
• In spiral traversal, re-check the bounds before the third and fourth edges, or a single-row/column remnant gets printed twice.
• For rotation, the transpose-then-reverse recipe avoids fragile four-way cyclic swaps.
• Mnemonic: "Rotate = transpose then flip."

Key formulas

• Full traversal of m×n matrix: O(mn) time.
• Element A[i][j] address (row-major) = base + (i·cols + j)·size.
• Transpose O(mn); matrix multiplication (n×n) O(n³) naive (Strassen O(n^2.81)).
• Rotate 90°: transpose then reverse each row (in-place O(n²), O(1) extra).
• Spiral/diagonal traversal: O(mn).
• Boundary and layer counts: layer k covers rows/cols k..n−1−k.

Usage: rotate a square matrix by transposing then reversing rows for O(1) extra space.

Worked Example

Problem: Give the spiral order traversal of the matrix
[[1, 2, 3], [4, 5, 6], [7, 8, 9]].

Solution: Maintain four boundaries — top, bottom, left, right — and peel layers inward: go right along the top row, down the right column, left along the bottom row, up the left column, then shrink the boundaries.

• Top row (left→right): 1, 2, 3 → top moves down.
• Right column (top→bottom): 6, 9 → right moves left.
• Bottom row (right→left): 8, 7 → bottom moves up.
• Left column (bottom→top): 4 → left moves right.
• Remaining center: 5.

Concatenating: 1, 2, 3, 6, 9, 8, 7, 4, 5.

Every cell is visited exactly once → O(m·n) time.

Answer: 1, 2, 3, 6, 9, 8, 7, 4, 5.