Spiral Matrix — InterviewPrepKit

Solving tips

Model the frontier with four boundaries top/bottom/left/right and consume one edge at a time, shrinking that boundary inward.
Loop while top<=bottom and left<=right; go right along top, down right, left along bottom, up left.
Re-check top<=bottom before the bottom row and left<=right before the left column so a lone leftover row/column is not emitted twice.
Target O(m*n) time and O(1) extra space beyond the output; the matrix may be rectangular so never reuse one dimension for both.

Problem

Given an m x n matrix, return a flat list of all its elements in spiral order: start at the top-left, go right across the top row, down the right column, left across the bottom row, up the left column, and continue inward until every cell has been visited exactly once.

Examples

[[1,2,3],[4,5,6],[7,8,9]] → [1,2,3,6,9,8,7,4,5] — around the outer ring clockwise, then the center.
[[1,2,3,4],[5,6,7,8],[9,10,11,12]] → [1,2,3,4,8,12,11,10,9,5,6,7] — a 3×4 spiral.
[[7]] → [7] — a single element.

Constraints

m == len(matrix), n == len(matrix[0])
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
The matrix need not be square — handle rectangular shapes and the moment the spiral collapses to a single remaining row or column.

Think about it first

Hint 1

Track four boundaries — `top`, `bottom`, `left`, `right`. Walk right along `top`, then down `right`, then left along `bottom`, then up `left`, shrinking the relevant boundary inward after each edge.

Hint 2

After finishing a top row, do `top += 1`; after a right column, `right -= 1`, and so on. Continue while `top <= bottom` and `left <= right`.

Hint 3

For a non-square matrix, the last ring can be a single row or single column. Re-check the boundary condition *between* the horizontal and vertical passes so you don't re-traverse a row or column that was already consumed.

TL;DR

Walk four shrinking boundaries (top/bottom/left/right) inward — O(m·n) time, O(1) extra space beyond the output.

Approach 1 — Direction simulation with a visited grid

The insight: you can literally “walk” the spiral. Move in the current direction (right → down → left → up, cycling) and turn whenever the next cell is off the grid or already seen. A boolean visited grid tells you when to turn.

from typing import List

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        visited = [[False] * n for _ in range(m)]
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # R, D, L, U
        r = c = d = 0
        result = []

        for _ in range(m * n):
            result.append(matrix[r][c])
            visited[r][c] = True
            nr, nc = r + directions[d][0], c + directions[d][1]
            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
                r, c = nr, nc
            else:
                d = (d + 1) % 4          # turn clockwise
                r += directions[d][0]
                c += directions[d][1]
        return result

Complexity: O(m·n) time, O(m·n) extra space for visited. Simple, but it allocates a second grid.

Approach 2 — Four shrinking boundaries (O(1) space)

The insight: you don’t need a visited grid — the four edges of the not-yet-emitted rectangle are the state. Keep top, bottom, left, right; emit the top row and drop it (top += 1), emit the right column and drop it (right -= 1), and so on. Re-check the loop condition between passes so a final lone row or column isn’t traversed twice.

from typing import List

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

        while top <= bottom and left <= right:
            for c in range(left, right + 1):        # top row, left → right
                result.append(matrix[top][c])
            top += 1

            for r in range(top, bottom + 1):        # right column, top → bottom
                result.append(matrix[r][right])
            right -= 1

            if top <= bottom:                       # bottom row, right → left
                for c in range(right, left - 1, -1):
                    result.append(matrix[bottom][c])
                bottom -= 1

            if left <= right:                       # left column, bottom → top
                for r in range(bottom, top - 1, -1):
                    result.append(matrix[r][left])
                left += 1

        return result

Walkthrough with [[1,2,3,4],[5,6,7,8],[9,10,11,12]] (top=0,bottom=2,left=0,right=3):

Top row 1,2,3,4 → top=1.
Right column (rows 1..2, col 3) 8,12 → right=2.
top(1) <= bottom(2): bottom row (cols 2..0) 11,10,9 → bottom=1.
left(0) <= right(2): left column (rows 1..1, col 0) 5 → left=1.
Loop again (top=1<=bottom=1, left=1<=right=2): top row (cols 1..2) 6,7 → top=2.
Right column: top(2) > bottom(1) range empty → right=1.
top(2) <= bottom(1) false, skip. left(1) <= right(1)… but now top > bottom so outer loop ends.
Result: [1,2,3,4,8,12,11,10,9,5,6,7]. Matches.

Complexity: O(m·n) time, O(1) extra space beyond the returned list.

Common pitfalls

Omitting the if top <= bottom / if left <= right guards before the bottom row and left column — on a single leftover row or column you’d emit it twice.
Off-by-one in the reversed ranges: bottom row goes range(right, left - 1, -1); the -1 bounds are easy to botch.
Assuming a square matrix — m and n differ, so never reuse one dimension for both.
Updating a boundary at the wrong time (before emitting its edge instead of after).

Pattern takeaway

For layered grid traversals, represent the frontier with a handful of boundary indices and shrink them as you consume each edge — no auxiliary grid needed. The recurring guard is to re-test the loop condition between the horizontal and vertical passes, since the innermost layer can degenerate to a single line.