Where it runs
1. The problem
A matrix is a table of values made of rows and columns. Sometimes you need to read every cell in a set order, or move every cell to a new place. Two classic moves do that: read the table in a clockwise spiral, and rotate the whole table a quarter turn clockwise.
Spiral: start at the top-left corner, walk the top row, go down the right column, walk the bottom row from right to left, go up the left column. Then step one ring inward and do the same. Keep going until every cell is read once.
Rotate: turn the table 90 degrees clockwise, so the top row becomes the right column.
In both moves you walk the table by its shape: you remember where the edges are now and move them as you go.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedspiralOrder([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 |
| 1 | 5 | 6 | 7 | 8 |
| 2 | 9 | 10 | 11 | 12 |
| 3 | 13 | 14 | 15 | 16 |
Read the matrix in a spiral. Four bounds mark the ring still to walk: top, bottom, left and right.
Recognise it
Say these words and it is this pattern
- 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
Looks similar, isn't
- 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.
An r by c grid gives O(rc), because each cell is visited once. Space is O(1) beyond the output.
On LeetCode
Matrix problems that read or write a grid ring by ring, or turn it a quarter turn. Four edge markers walk the outer ring and then move inward, and a turn sends cell (i, j) to (j, R minus 1 minus i).
Copy cell (i, j) to (j, i) in a new grid with rows and columns swapped.
Turn mat up to four times with the lesson's rotate90 and compare it with target after each turn.
The lesson's spiralOrder, with the guard for a lone row or column.
The same four markers walk the spiral and write the numbers 1 to n^2.
LeetCode wants the turn in place, so transpose the matrix and then reverse each row.