Matrix traversal (spiral / diagonal)

How does Matrix traversal (spiral / diagonal) work?

A spiral keeps four bounds: top, bottom, left and right. They close inward as each ring finishes.

Walk the top row from left to right, then move the top bound down. That row is now used up.

Walk the right column, then the bottom row, then the left column. Each walk shrinks its own bound.

Check the bounds before the last two walks. A single leftover row would otherwise be walked twice.

A diagonal walk groups cells by the sum of their two indices. Every cell on one diagonal shares that sum.

The direction flips on each successive diagonal. That is what produces the zigzag.

1. top row: 1, 2, 3A three by three grid, walked as a spiral.
2. right column: 6, 9Top to bottom, then the right bound moves left.
3. bottom row: 8, 7Right to left, then the bottom bound moves up.
4. left column: 4Bottom to top, then the left bound moves right.
5. centre: 5One cell is left. The four bounds have met.

function spiralOrder(matrix) {
    const result = [];
    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;
    while (top <= bottom && left <= right) {
        for (let c = left; c <= right; c++) result.push(matrix[top][c]);
        for (let r = top + 1; r <= bottom; r++) result.push(matrix[r][right]);
        if (top < bottom) for (let c = right - 1; c >= left; c--) result.push(matrix[bottom][c]);
        if (left < right) for (let r = bottom - 1; r > top; r--) result.push(matrix[r][left]);
        top++; bottom--; left++; right--;
    }
    return result;
}

A worked example of Matrix traversal (spiral / diagonal)

Rotate a square matrix in place

Rotate an n by n matrix ninety degrees clockwise, in place.

Allocating a second matrix is not allowed.

Transpose it first, swapping each cell with its mirror across the diagonal.

Then reverse every row. Those two moves together make a rotation.

function rotate(matrix) {
    const n = matrix.length;

    // transpose: j starts at i + 1, so no swap is undone
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }

    for (const row of matrix) row.reverse();

    return matrix;
}

When should you use Matrix traversal (spiral / diagonal)?

These phrases in a problem statement point here:

• •read or fill a grid in spiral order
• •walk a matrix diagonal by diagonal
• •rotate a matrix 90 degrees
• •visit every cell in a fixed geometric order

What is Matrix traversal (spiral / diagonal) confused with?

• Matrix search (sorted grid): That uses the sorted order to skip most of the grid. This one visits every single cell.
• Matrix word search (grid DFS/backtracking): That searches with backtracking and can turn around. Here the path is fixed in advance.
• Graph BFS / DFS: A traversal follows edges out from a start node. Here the order comes from geometry.
• In-place array transform: Rotating a matrix in place is that idea in two dimensions. The buffer rule is the same.

Common mistakes with Matrix traversal (spiral / diagonal)

• Transposing over the whole grid

  Every swap is then undone by its own mirror. Start the inner loop at i plus one.

• Walking a leftover row twice

  A single middle row gets read forwards and then backwards. Check the bounds before the last two walks.

• Assuming the grid is square

  A spiral over a wide grid runs out of columns first. Bounds handle that, a fixed loop count does not.

• Swapping row and column indices

  The usual order is matrix row then column. Swapping them silently transposes everything.

Which interview problems use Matrix traversal (spiral / diagonal)?

• Spiral matrix: Four bounds that close inward ring by ring.
• Spiral matrix II: Fill a grid in that order instead of reading it.
• Rotate image: Transpose, then reverse each row.
• Diagonal traverse: Group the cells by the sum of their indices.
• Set matrix zeroes: Use the first row and column as the marks.
• Transpose matrix: The building block that a rotation is made of.
• Zigzag conversion: The same alternating direction, over a string.

What is the time and space complexity of Matrix traversal (spiral / diagonal)?

O(mn)

An r by c grid gives O(rc), because each cell is visited once. Space is O(1) beyond the output.