You get a matrix of rows × columns numbers. Return all of them in spiral order: along the top row to the right, down the right column, back along the bottom row, up the left column, and then the same again on the ring inside, until every number is taken once. Our example: 3 × 5, [1, 2, 3, 4, 5], [12, 13, 14, 15, 6], [11, 10, 9, 8, 7]. It is numbered along the spiral, so the answer counts up: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15].
54 Spiral MatrixWalkthrough · 1×
Example: 3 × 5, wider than tall: after the outer ring only one row is left, and the check in the middle of the loop stops it from being read a second time.
not read yetjust addedin outwould be added twice without the checkthe answer
Start with an empty out
01/30
restart · back · play · step
Speed
1functionspiralOrder(m):
2 out = []
3 top, bottom = 0, rows - 1
4 left, right = 0, cols - 1
5while top <= bottom and left <= right:
6for c from left to right: add m[top][c]
7 top = top + 1
8for r from top to bottom: add m[r][right]
9 right = right - 1
10if top > bottom or left > right: break
11for c from right downto left: add m[bottom][c]
12 bottom = bottom - 1
13for r from bottom downto top: add m[r][left]
14 left = left + 1
15return out
state
out
[]
top
–
bottom
–
left
–
right
–
historyclick a step to go back
← → step · space play/pause
Why it works
The four boundaries always frame exactly the cells not read yet. Each side reads one edge of that frame and moves its boundary in by one, so no cell is read twice and none is skipped.
After the top row and the right column the frame may already be empty: one row or one column was all that was left. The check before the bottom row catches this; without it the bottom row would be the same row again, read backwards.
The loop ends when the boundaries cross: top passes bottom or left passes right. Then there is nothing between them.
Complexity
Time O(rows × columns): every cell is read once. Memory O(1) besides the answer itself: four boundaries.