LeetCode #54 Medium

Spiral Matrix

Return every element of an m x n matrix in clockwise spiral order.

arraymatrixsimulation

02

Intuition

💡

You will write the four sweeps, test it on a square matrix, watch it pass, and ship it. Then a 3x4 or a single-row matrix comes along and a whole row appears twice in your output. The reason is that you only check top <= bottom and left <= right at the top of the while loop, but the boundaries move three times inside one iteration. On a thin remainder the top sweep consumes the last row and pushes top past bottom, and the bottom sweep then re-reads that exact same row because nobody re-checked. The fix is not clever, it is disciplined: re-test top <= bottom immediately before the bottom sweep, and left <= right immediately before the left sweep. The invariant you are protecting is that the rectangle bounded by the four walls always contains exactly the cells not yet emitted, so a sweep is only legal while that rectangle is still non-empty.

03

Approach

1

Four walls, not four directions

Rather than tracking a heading and turning, keep four integers: top, bottom, left and right. They fence off the sub-rectangle that has not been read yet. Each of the four sweeps reads one full wall of that rectangle and then retracts its own boundary inward by one. Thinking in walls rather than turns is what makes the termination condition expressible at all: the spiral is finished exactly when the rectangle becomes empty.

2

Sweep, then retract, in a fixed order

Go left-to-right along the top row and increment top; top-to-bottom along the right column and decrement right; right-to-left along the bottom row and decrement bottom; bottom-to-top along the left column and increment left. Emitting before retracting matters, because the retraction is what marks those cells as consumed. Doing it in the other order would skip a wall on the first pass.

3

Re-check the walls mid-loop

This is the part everyone gets wrong. After the first two sweeps, top and right have already moved, so the loop condition tested at the top of the iteration is stale. Guard the bottom sweep with top <= bottom and the left sweep with left <= right. Without them, a matrix with a single remaining row or column emits that row or column twice, because the return sweep walks back over ground the outbound sweep already covered.

04

Solution & live demo

python

▶1class Solution:
▶2    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
▶3        if not matrix or not matrix[0]:
▶4            return []
▶5        top, bottom = 0, len(matrix) - 1
▶6        left, right = 0, len(matrix[0]) - 1
▶7        out = []
▶8        while top <= bottom and left <= right:
▶9            for c in range(left, right + 1):
▶10                out.append(matrix[top][c])
▶11            top += 1
▶12            for r in range(top, bottom + 1):
▶13                out.append(matrix[r][right])
▶14            right -= 1
▶15            if top <= bottom:
▶16                for c in range(right, left - 1, -1):
▶17                    out.append(matrix[bottom][c])
▶18                bottom -= 1
▶19            if left <= right:
▶20                for r in range(bottom, top - 1, -1):
▶21                    out.append(matrix[r][left])
▶22                left += 1
▶23        return out

05

Edge cases

Empty matrix or empty first row

Return an empty list before entering the loop; matrix[0] would otherwise raise.

Single row, e.g. [[1,2,3,4]]

The top sweep takes everything and pushes top past bottom; the mid-loop guard skips the bottom sweep so nothing is duplicated.

Single column, e.g. [[1],[2],[3]]

Top then right sweeps take everything and right falls below left; the left-sweep guard prevents a second pass.

Non-square matrix such as 3x4

Rows and columns exhaust at different times, so the two guards fire independently rather than together.

06

Complexity

Time

O(m * n)

Space

O(1)

Every cell is appended exactly once; the output list itself is not counted as extra space.