LeetCode 54 - Spiral Matrix

This Medium matrix problem returns every cell in clockwise spiral order. Instead of shrinking four explicit boundaries, I modeled the traversal with a current position and direction, turning clockwise whenever the next cell was outside the matrix or already visited.

---

Problem link and explanation

• Problem: 54. Spiral Matrix
• Summary: Given an m by n matrix, return all elements by moving right, down, left, and up in a spiral until every cell has been visited.

Each cell must enter the result exactly once. The traversal changes direction when its next coordinate is invalid or has already been processed, and it stops when the output contains m * n values.

---

Approach

Direction indices 0 through 3 represent right, down, left, and up. The row and column delta arrays calculate the next coordinate for the current direction.

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

next_row = row + dr[dir]
next_col = col + dc[dir]

If the next coordinate is out of bounds or marked as visited, (dir + 1) % 4 performs a clockwise turn. I used -200 as the marker because it falls outside the problem’s allowed cell values.

if (
    next_row < 0
    or next_row >= n
    or next_col < 0
    or next_col >= m
    or matrix[next_row][next_col] == VISIT
):
    dir = (dir + 1) % 4

matrix[row][col] = VISIT

This choice mutates the input matrix. If callers needed the original data after the traversal, I would use a separate visited structure or the alternative approach that shrinks top, bottom, left, and right boundaries.

---

Complexity analysis

• Time complexity: O(m × n)
  • Every cell is appended to the output once.
• Space complexity: O(1) excluding the returned array
  • The algorithm stores its visited state in the input and uses only fixed-size direction arrays and position variables.

---

Implementation code

from typing import List

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        answer = []

        dir = 0
        row = 0
        col = 0

        n = len(matrix)
        m = len(matrix[0])
        size = n * m

        VISIT = -200
        dr = [0, 1, 0, -1]
        dc = [1, 0, -1, 0]

        while len(answer) < size:
            item = matrix[row][col]
            answer.append(item)

            next_row = row + dr[dir]
            next_col = col + dc[dir]

            if (
                next_row < 0
                or next_row >= n
                or next_col < 0
                or next_col >= m
                or matrix[next_row][next_col] == VISIT
            ):
                dir = (dir + 1) % 4

            matrix[row][col] = VISIT

            row += dr[dir]
            col += dc[dir]

        return answer

---

Summary and reflection

The spiral becomes a single simulation rule: continue forward while the next cell is available, otherwise turn clockwise. That rule works for rectangular matrices without splitting the traversal into separate loops for each edge. Reusing the matrix for visited state keeps auxiliary space constant, but it also makes input mutation part of the algorithm’s contract rather than a free optimization.