Spiral Matrix · DSA Prep

A spiral walk is just “go right along the top, down along the right side, left along the bottom, up along the left side, then shrink the boundary and repeat.” The only real work is bookkeeping so you never re-visit a cell and you stop cleanly once the boundary collapses.

Direction Vector + Visited Grid

Time O(m·n)Space O(m·n)

Walk in one of four directions, keeping a visited grid so you know when to turn. At each step try to continue in the current direction; if that would leave the grid or land on a visited cell, rotate 90° clockwise (right → down → left → up → right) instead. Stop after collecting m * n cells.

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)]
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # right, down, left, up
        r = c = d = 0
        result = []
        for _ in range(m * n):
            result.append(matrix[r][c])
            visited[r][c] = True
            nr, nc = r + dirs[d][0], c + dirs[d][1]
            if not (0 <= nr < m and 0 <= nc < n and not visited[nr][nc]):
                d = (d + 1) % 4
                nr, nc = r + dirs[d][0], c + dirs[d][1]
            r, c = nr, nc
        return result

Correctness: the visited grid guarantees the walk never repeats a cell, and turning clockwise exactly when blocked reproduces the spiral shape. Complexity: every cell is visited exactly once → O(m·n) time, but the visited grid costs as much memory as the input itself → O(m·n) space.

Shrinking Boundaries

OptimalTime O(m·n)Space O(1)

Track four boundaries — top, bottom, left, right. Peel off the top row, then the right column, then the bottom row, then the left column, moving each boundary inward after its pass. The if top <= bottom / if left <= right guards before the last two passes are what prevent single-row or single-column matrices from double-counting a row or column that the first two passes already consumed.

class Solution:
    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
        result = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1
        while top <= bottom and left <= right:
            for c in range(left, right + 1):
                result.append(matrix[top][c])
            top += 1
            for r in range(top, bottom + 1):
                result.append(matrix[r][right])
            right -= 1
            if top <= bottom:
                for c in range(right, left - 1, -1):
                    result.append(matrix[bottom][c])
                bottom -= 1
            if left <= right:
                for r in range(bottom, top - 1, -1):
                    result.append(matrix[r][left])
                left += 1
        return result

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

top = 0bottom = 2left = 0right = 2

1 / 6

seenresultcurrent

Walk the top row left to right: 1, 2, 3. Move top down to 1.

After the fourth pass the boundaries shrink to top = bottom = left = right = 1 — a single remaining cell. The loop runs once more, its top-row pass collects that lone 5, top advances past bottom, and the while top <= bottom and left <= right check fails, ending the walk.

Complexity: each of the four passes only visits cells that have not been visited before, and together the passes cover the grid exactly once → O(m·n) time, O(1) extra space (excluding the output list).