CodeWithYash

Foundation · Module 3 · Lesson 5

Matrix traversal

Rows, columns, diagonals, spiral, and boundary walks.

15–25 min readLesson 17 of 123

Lesson 17 of 123

1d streak

2D Matrix Memory Layout & Traversal Strategies

A 2D array or matrix is mathematically a grid of rows and columns, but physical computer hardware is linear 1-dimensional RAM. In languages like C/C++ and in modern memory buffers, 2D matrices are stored in Row-Major Order: row 0 is laid out first, followed immediately by row 1, row 2, and so on.

Flattened 2D Indexing Formula
Matrix Grid (2 rows x 3 cols):
       Col 0  Col 1  Col 2
Row 0: [ 10 ][ 20 ][ 30 ]
Row 1: [ 40 ][ 50 ][ 60 ]

Flattened in RAM:
Index:   0    1    2    3    4    5
Value: [ 10 | 20 | 30 | 40 | 50 | 60 ]

Conversion Formulas:
Flatten 2D to 1D:  flatIndex = (row * cols) + col
Recover 2D from 1D: row = flatIndex / cols,  col = flatIndex % cols

Cache Locality in 2D Matrix Iteration

Always iterate rows first, then columns (matrix[r][c]). Iterating columns first (matrix[c][r]) jumps across memory by cols * elementSize bytes on every step, discarding CPU cache lines and running up to 5-10x slower on large grids!
SpiralMatrixTraversal.java
// Classic Spiral Traversal: Layer-by-Layer Boundary Shrinking
public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix.length == 0) return result;

    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;

    while (top <= bottom && left <= right) {
        // 1. Traverse top row (left to right)
        for (int c = left; c <= right; c++) result.add(matrix[top][c]);
        top++;

        // 2. Traverse right column (top to bottom)
        for (int r = top; r <= bottom; r++) result.add(matrix[r][right]);
        right--;

        // 3. Traverse bottom row (right to left)
        if (top <= bottom) {
            for (int c = right; c >= left; c--) result.add(matrix[bottom][c]);
            bottom--;
        }

        // 4. Traverse left column (bottom to top)
        if (left <= right) {
            for (int r = bottom; r >= top; r--) result.add(matrix[r][left]);
            left++;
        }
    }
    return result;
}

Cost Model

Complexity & Trade-offs

Visit every cell
O(rows × cols)
O(1)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Contiguous data, strings, matrix grids, and in-place transformations.
  • Problems where indexes encode processed regions.
  • Cache-friendly scans and compact storage.

Common mistakes

  • Using a stale index after insertion, deletion, or a boundary move.
  • Overwriting a value before it has been consumed.
  • Assuming a matrix is square or a string is mutable.

Practice prompts

  • Reproduce the worked Matrix traversal example without looking at the trace.
  • Change one input condition and explain whether the Matrix traversal invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.