The problem
Return all numbers of a grid in spiral order: along the top row, down the right column, back along the bottom, up the left, then inward.
Input: 1,2,3,4 / 5,6,7,8 / 9,10,11,12 Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
Picture it
Picture a snail crawling over a tiled garden. Four walls (top, bottom, left, right) mark the unvisited area. After the snail finishes a side, that wall moves one step inward. When the walls cross, every tile has been visited.
How to recognise it
- You must visit every cell of a grid in a fixed non-row order, here a spiral.
- The path goes in a direction until it hits an edge or a visited cell, then turns clockwise.
- Once a side has been walked, that row or column is never needed again.
- Grids are small (up to 10 × 10), so the challenge is getting the edges right, not speed.
- The grid may be a single row, a single column or any rectangle.
Start with brute force
Simulate a walker. Keep a grid of visited marks, move in the current direction, and turn right whenever the next cell is outside the grid or already visited.
def spiral_brute(m):
R, C = len(m), len(m[0])
seen = [[False] * C for _ in range(R)]
out = []
r = c = 0
dr, dc = 0, 1 # start by moving right
for _ in range(R * C):
out.append(m[r][c])
seen[r][c] = True
nr, nc = r + dr, c + dc
if not (0 <= nr < R and 0 <= nc < C) or seen[nr][nc]:
dr, dc = dc, -dr # turn clockwise
nr, nc = r + dr, c + dc
r, c = nr, nc
return out
This is correct and runs in O(R · C) time, so time is not the problem. It uses O(R · C) extra space for the visited grid, and the direction-turning rule is easy to get wrong. The boundary version removes both.
From brute force to the idea
- Replace visited marks with four walls.
top,bottom,leftandrightmark the rectangle of cells not yet visited. - Walk one side, then move that wall inward. Walk the top row from
lefttoright, thentop += 1. Walk the right column fromtoptobottom, thenright -= 1. - Walk back along the bottom and up the left, each followed by moving its wall.
- Guard the last two sides. After the top row and right column have shrunk the rectangle, it may be empty or a single line. The checks
top <= bottomandleft <= rightstop the code from walking a row or column twice. - Stop when the walls cross. The
whilecondition ends the loop once there are no cells left.
This is the key idea: four shrinking boundaries replace the visited grid, and the two if checks handle the leftover single row or column.
The key idea
Four boundaries that shrink after each side. O(rows × cols).
Python solution
def spiral_order(m):
out = []
top, bottom, left, right = 0, len(m) - 1, 0, len(m[0]) - 1
while top <= bottom and left <= right:
for c in range(left, right + 1): out.append(m[top][c])
top += 1
for r in range(top, bottom + 1): out.append(m[r][right])
right -= 1
if top <= bottom:
for c in range(right, left - 1, -1): out.append(m[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1): out.append(m[r][left])
left += 1
return outIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (visited grid) | O(R · C): each cell is placed once | O(R · C) for the visited marks, plus the output |
| Shrinking boundaries (shown code) | O(R · C): each cell is appended once | O(1) extra beyond the output list |
Edge cases
- One cell (
[[1]]): returns[1]. - One row (
[[1, 2, 3]]): the top loop adds all three and thetop <= bottomcheck stops a second pass, so the result is[1, 2, 3]. - One column (
[[1], [2], [3]]): the right-column loop adds 2 and 3, and theleft <= rightcheck stops the walk back up, so the result is[1, 2, 3]. - 2 × 2 (
[[1, 2], [3, 4]]): returns[1, 2, 4, 3]. - Odd square (3 × 3 with 1 to 9): the centre 5 is the last cell, giving
[1, 2, 3, 6, 9, 8, 7, 4, 5]. - Empty list:
len(m[0])raisesIndexError, but the problem promises at least one row and column.
Common mistakes
- Dropping the two guard checks. A single row then returns
[1, 2, 3, 2, 1]and a single column returns[1, 2, 3, 2], with cells repeated. - Using
top < bottom and left < rightin thewhile, which skips the middle row or column of a grid like 3 × 3 and returns only 8 of the 9 cells. - Forgetting to move a wall after walking its side, which walks the same cells again.
- Using
range(right, left, -1)and missing the last cell of the bottom row.
Given n, build an n × n grid filled with 1 to n² in spiral order, clockwise from the top left. For n = 3 the grid is [[1, 2, 3], [8, 9, 4], [7, 6, 5]]. Describe your approach, then write it if you like.
Compare with our answer
Use the same four walls, but write a counter into the cells instead of reading them.
def spiral_fill(n):
g = [[0] * n for _ in range(n)]
top, bottom, left, right = 0, n - 1, 0, n - 1
k = 1
while top <= bottom and left <= right:
for c in range(left, right + 1): g[top][c] = k; k += 1
top += 1
for r in range(top, bottom + 1): g[r][right] = k; k += 1
right -= 1
if top <= bottom:
for c in range(right, left - 1, -1): g[bottom][c] = k; k += 1
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1): g[r][left] = k; k += 1
left += 1
return g
spiral_fill(1) is [[1]], and spiral_order(spiral_fill(n)) gives 1, 2, ..., n² for every n up to 7. Time and space O(n²).
A strong answer mentions: the same four boundaries, a counter instead of reads, and why the two guards still matter for the odd-size centre.
1. You must print the cells of a rectangular grid in an outside-in clockwise spiral. Which approach fits best?
Four shrinking walls give the spiral directly and need no extra memory. Reversing alternate rows gives a zig-zag, not a spiral.
2. What do the checks if top <= bottom and if left <= right protect against?
After the first two sides, the remaining rectangle can be one row or one column. Without the checks, the code walks it back and repeats cells.
3. A learner removes both if guards from the shown code. What does spiral_order([[1, 2, 3]]) return?
After the top row, right is 1, and without the guard the bottom loop still walks back from column 1 to column 0, adding 2 and 1 again. Running the variant gives [1, 2, 3, 2, 1].
Score 60% or more and the lesson is marked complete.