LeetCode 54: Spiral Matrix

Problem Restatement

We are given an m x n matrix.

We need to return all elements of the matrix in spiral order.

The spiral starts at the top-left cell. It moves:

1. Right across the top row
2. Down the right column
3. Left across the bottom row
4. Up the left column

Then it repeats the same pattern on the inner part of the matrix.

The official constraints are 1 <= m, n <= 10 and -100 <= matrix[i][j] <= 100.

Input and Output

Function shape:

def spiralOrder(matrix: list[list[int]]) -> list[int]:
    ...

Examples

For:

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]

The spiral order is:

[1, 2, 3, 6, 9, 8, 7, 4, 5]

We first read the top row:

1, 2, 3

Then the right column:

6, 9

Then the bottom row from right to left:

8, 7

Then the left column from bottom to top:

4

Finally, the center:

5

For:

matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
]

The answer is:

[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

First Thought: Simulate Movement

One way is to simulate the actual movement.

Start at (0, 0).

Move right until the next cell is outside the matrix or already visited. Then turn down. Then turn left. Then turn up. Repeat until all cells have been visited.

This works, but it needs a visited matrix or it needs to modify the input matrix.

There is a cleaner approach.

Key Insight

A spiral traversal reads the matrix layer by layer.

Each layer has four boundaries:

For each layer:

1. Read the top row from left to right.
2. Move top down.
3. Read the right column from top to bottom.
4. Move right left.
5. Read the bottom row from right to left, if it still exists.
6. Move bottom up.
7. Read the left column from bottom to top, if it still exists.
8. Move left right.

The checks before reading the bottom row and left column matter because rectangular matrices can collapse into a single row or a single column.

Algorithm

Initialize:

top = 0
bottom = len(matrix) - 1
left = 0
right = len(matrix[0]) - 1
ans = []

While the boundaries are valid:

top <= bottom and left <= right

Read in four directions:

1. Top row: columns left to right.
2. Right column: rows top to bottom.
3. Bottom row: columns right to left, only if top <= bottom.
4. Left column: rows bottom to top, only if left <= right.

Return ans.

Correctness

The algorithm keeps four boundaries around the unvisited part of the matrix.

Reading the top row visits every cell on the current top edge exactly once, then top moves inward. Reading the right column visits every cell on the current right edge exactly once, then right moves inward.

After those two moves, the remaining unvisited region may have no rows or no columns. The algorithm checks the boundaries before reading the bottom row and left column. This prevents duplicate visits in single-row and single-column cases.

Each loop removes one outer layer from the unvisited rectangle. Since every cell belongs to exactly one such layer, every cell is added once. The order of adding cells follows right, down, left, and up, so the returned list is exactly the spiral order.

Complexity

The output list stores m * n values, which is required by the problem.

Implementation

class Solution:
    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
        top = 0
        bottom = len(matrix) - 1
        left = 0
        right = len(matrix[0]) - 1

        ans = []

        while top <= bottom and left <= right:
            for col in range(left, right + 1):
                ans.append(matrix[top][col])
            top += 1

            for row in range(top, bottom + 1):
                ans.append(matrix[row][right])
            right -= 1

            if top <= bottom:
                for col in range(right, left - 1, -1):
                    ans.append(matrix[bottom][col])
                bottom -= 1

            if left <= right:
                for row in range(bottom, top - 1, -1):
                    ans.append(matrix[row][left])
                left += 1

        return ans

Code Explanation

We start with the whole matrix as the unvisited rectangle:

top = 0
bottom = len(matrix) - 1
left = 0
right = len(matrix[0]) - 1

The loop continues while there is still a valid rectangle:

while top <= bottom and left <= right:

First, read the top row:

for col in range(left, right + 1):
    ans.append(matrix[top][col])
top += 1

After reading it, that row is consumed, so top moves down.

Next, read the right column:

for row in range(top, bottom + 1):
    ans.append(matrix[row][right])
right -= 1

After reading it, that column is consumed, so right moves left.

Before reading the bottom row, check that a row still remains:

if top <= bottom:

Then read from right to left:

for col in range(right, left - 1, -1):
    ans.append(matrix[bottom][col])
bottom -= 1

Before reading the left column, check that a column still remains:

if left <= right:

Then read from bottom to top:

for row in range(bottom, top - 1, -1):
    ans.append(matrix[row][left])
left += 1

When the boundaries cross, all cells have been visited.

Testing

def run_tests():
    s = Solution()

    assert s.spiralOrder([
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
    ]) == [1, 2, 3, 6, 9, 8, 7, 4, 5]

    assert s.spiralOrder([
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12],
    ]) == [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

    assert s.spiralOrder([[1]]) == [1]

    assert s.spiralOrder([[1, 2, 3]]) == [1, 2, 3]

    assert s.spiralOrder([
        [1],
        [2],
        [3],
    ]) == [1, 2, 3]

    assert s.spiralOrder([
        [1, 2],
        [3, 4],
    ]) == [1, 2, 4, 3]

    print("all tests passed")

run_tests()