LeetCode 54 · Math & Geometry

Spiral Matrix, explained with a picture

A snail spiralling inward across a tiled garden.

MediumMath & Geometry
▶ Watch it step by step

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

  1. Replace visited marks with four walls. top, bottom, left and right mark the rectangle of cells not yet visited.
  2. Walk one side, then move that wall inward. Walk the top row from left to right, then top += 1. Walk the right column from top to bottom, then right -= 1.
  3. Walk back along the bottom and up the left, each followed by moving its wall.
  4. 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 <= bottom and left <= right stop the code from walking a row or column twice.
  5. Stop when the walls cross. The while condition 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 out

In 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

ApproachTimeSpace
Brute force (visited grid)O(R · C): each cell is placed onceO(R · C) for the visited marks, plus the output
Shrinking boundaries (shown code)O(R · C): each cell is appended onceO(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 the top <= bottom check 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 the left <= right check 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]) raises IndexError, 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 < right in the while, 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.
Your turn: fill a spiral

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.

Check what stuck

1. You must print the cells of a rectangular grid in an outside-in clockwise spiral. Which approach fits best?

2. What do the checks if top <= bottom and if left <= right protect against?

3. A learner removes both if guards from the shown code. What does spiral_order([[1, 2, 3]]) return?

Score 60% or more and the lesson is marked complete.