Spiral Matrix

Return matrix values in spiral order.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Spiral Matrix: Read one side of the current rectangle at a time, shrink that boundary, and guard sides that may have disappeared.

Input and goalReturn matrix values in spiral order.

Initialize the outer rectangleFor the 3x4 matrix, start top=0, bottom=2, left=0, right=3 with an empty answer.

1read cursor23456789101112

boundariestop=0 bottom=2 left=0 right=3answer[]

Recognize it

Use boundary peeling when a rectangular grid must be traversed layer by layer around its perimeter in directional order.

Keep true

At each while-loop entry, every cell outside top..bottom and left..right has been emitted exactly once, and every unvisited cell lies inside that closed rectangle.

Reuse it

For perimeter traversals, represent remaining work as explicit inclusive bounds, consume one edge, shrink it immediately, and guard later edges because earlier moves may collapse the region.

Pattern: Shrinking top, bottom, left, and right boundaries.

Simple idea: Read the top row, right column, bottom row, and left column. Move each used boundary inward. Check that a row or column still exists before reading it.

def spiral_order(matrix: list[list[int]]) -> list[int]:
   if not matrix or not matrix[0]:
      return []

   answer = []
   top, bottom = 0, len(matrix) - 1
   left, right = 0, len(matrix[0]) - 1

   while top <= bottom and left <= right:
      answer.extend(matrix[top][left : right + 1])
      top += 1

      for row in range(top, bottom + 1):
         answer.append(matrix[row][right])
      right -= 1

      if top <= bottom:
         answer.extend(reversed(matrix[bottom][left : right + 1]))
         bottom -= 1
      if left <= right:
         for row in range(bottom, top - 1, -1):
            answer.append(matrix[row][left])
         left += 1

   return answer

Cost: $O(rows\times cols)$ time and $O(1)$ extra space, not counting the answer.