Spiral Matrix

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.

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

Watch the boundary frame shrink one side at a time, and note the two guards: they are what stop a crossed boundary from walking a row or column that a previous pass already consumed.

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).