Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Spiral Matrix
• Main tags: Array, Matrix, Simulation

What the problem is really asking

The input is a 2D matrix. The task is to return every value exactly once in spiral order:

• go left to right across the top
• then top to bottom down the right side
• then right to left across the bottom
• then bottom to top up the left side
• keep repeating until there is nothing left

This is a traversal problem. Nothing in the matrix needs to be modified. The only challenge is knowing when to turn and when a side has already been fully consumed.

The clean mental model

The easiest way to think about the matrix is as a set of shrinking layers.

Each loop removes one outer ring:

1. read the top row
2. read the right column
3. read the bottom row in reverse
4. read the left column in reverse

After that:

• the top boundary moves down
• the right boundary moves left
• the bottom boundary moves up
• the left boundary moves right

Then the same pattern repeats on the smaller inner rectangle.

How to derive the optimal solution

A natural first idea is:

• walk in the current direction
• turn when the next step goes out of bounds or hits a visited cell
• mark every visited cell

That works, but it uses extra memory for the visited grid.

The better observation is that the algorithm never really needs to know every visited cell individually. It only needs to know the current outer border of the remaining rectangle.

So instead of tracking visited cells, track four boundaries:

• top
• bottom
• left
• right

Whenever one side is finished, move that boundary inward. That gives the same spiral behavior with constant extra space.

The important edge-case detail

The bottom-row pass and the left-column pass must be guarded.

Why? Because after reading the top row and right column, the remaining rectangle might already be empty.

That happens in cases like:

• a single row
• a single column
• the final inner layer of an odd-shaped matrix

So the safe pattern is:

• only read the bottom row if top <= bottom
• only read the left column if left <= right

Those two checks prevent duplicates.

Best approach

The boundary-shrinking simulation is the right default solution:

• Time: O(m * n)
• Extra space: O(1) excluding the output list
• Why it is optimal: every element must be visited at least once, so O(m * n) time is unavoidable

Python solution

from typing import List


def spiral_traversal(matrix: List[List[int]]) -> List[int]:
    """Return the matrix values in clockwise spiral order."""
    if not matrix or not matrix[0]:
        return []

    spiral_order: List[int] = []
    top_row = 0
    bottom_row = len(matrix) - 1
    left_col = 0
    right_col = len(matrix[0]) - 1

    while top_row <= bottom_row and left_col <= right_col:
        # Traverse the current top row from left to right.
        for col in range(left_col, right_col + 1):
            spiral_order.append(matrix[top_row][col])
        top_row += 1

        # Traverse the current right column from top to bottom.
        for row in range(top_row, bottom_row + 1):
            spiral_order.append(matrix[row][right_col])
        right_col -= 1

        # If rows remain, traverse the current bottom row from right to left.
        if top_row <= bottom_row:
            for col in range(right_col, left_col - 1, -1):
                spiral_order.append(matrix[bottom_row][col])
            bottom_row -= 1

        # If columns remain, traverse the current left column from bottom to top.
        if left_col <= right_col:
            for row in range(bottom_row, top_row - 1, -1):
                spiral_order.append(matrix[row][left_col])
            left_col += 1

    return spiral_order


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

Why this works

At every moment, top_row, bottom_row, left_col, and right_col describe the smallest rectangle that still has unread cells.

One full loop reads that rectangle’s outer boundary exactly once, then shrinks the rectangle inward.

Because each cell belongs to exactly one layer and is appended once, the output is correct and complete.

The interview version to remember is:

peel the matrix layer by layer using four moving boundaries.