Spiral Matrix

Medium#54spiral

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.

01234012123451213141561110987out
not read yetjust addedin outwould be added twice without the checkthe answer

Start with an empty out

01/30
restart · back · play · step
Speed
1function spiralOrder(m):
2 out = []
3 top, bottom = 0, rows - 1
4 left, right = 0, cols - 1
5 while top <= bottom and left <= right:
6 for c from left to right: add m[top][c]
7 top = top + 1
8 for r from top to bottom: add m[r][right]
9 right = right - 1
10 if top > bottom or left > right: break
11 for c from right down to left: add m[bottom][c]
12 bottom = bottom - 1
13 for r from bottom down to top: add m[r][left]
14 left = left + 1
15 return out
state
out
[]
top
–
bottom
–
left
–
right
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. 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.
  2. 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.
  3. 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.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.