AlgoMaster Logo

Spiral Matrix

mediumFrequency8 min readUpdated June 23, 2026

Understanding the Problem

Spiral traversal sounds simple but is easy to get wrong while coding. There is no special algorithm or data structure involved. It is pure simulation, and the difficulty is managing boundaries and direction changes without off-by-one errors.

The traversal walks the matrix like a maze, always hugging the outer wall. Start at the top-left corner and move right. On reaching the edge, or a cell already visited, turn clockwise: right becomes down, down becomes left, left becomes up, up becomes right again. Keep walking and turning until every cell has been visited.

Two questions drive the implementation: how do we know when to turn, and how do we avoid visiting a cell twice? There are two ways to handle this, and both produce the same result with different space trade-offs.

Key Constraints:

  • 1 <= m, n <= 10, so the matrix has at most 100 elements. The problem is about correctness, not performance.
  • Values range from -100 to 100, so there is no overflow concern.
  • The lower bound of 1 guarantees at least one row and one column, so matrix[0] is always safe to read.
  • Both solutions run in O(m * n), which is optimal since every cell must be visited once.

Approach 1: Simulation with Direction Arrays

Intuition

Simulate the spiral walk directly. At any moment we sit at some position moving in some direction. When the next step would leave the matrix or land on an already-visited cell, we turn clockwise and continue.

A visited matrix records which cells we have already added. A direction array cycles through right, down, left, up. When the next cell in the current direction is invalid, we rotate to the next direction. Because the spiral only ever turns clockwise, advancing the direction index by one each time is enough; we never need to skip two directions at once.

Algorithm

  1. Create a visited boolean matrix of the same size, initialized to false.
  2. Define direction vectors: {0,1} (right), {1,0} (down), {0,-1} (left), {-1,0} (up).
  3. Start at position (0, 0) with direction index 0 (right).
  4. For each of the m * n steps:
    1. Add the current cell's value to the result and mark it as visited.
    2. Compute the next position using the current direction.
    3. If the next position is out of bounds or already visited, rotate the direction index clockwise (increment mod 4), then recompute the next position.
    4. Move to the next position.
  5. Return the result list.

Example Walkthrough

Trace the 3x3 matrix:

Directions are indexed 0=right, 1=down, 2=left, 3=up. Start at (0,0), dir=0.

The result is [1,2,3,6,9,8,7,4,5]. At step 8 the turn is forced by the visited cell (0,0) rather than by an edge, which is the case the visited matrix exists to catch.

Code

The simulation approach is straightforward to reason about, but it allocates an entire m x n boolean grid to remember visited cells. The next approach removes that grid by tracking the boundaries of the unvisited region and shrinking them as the spiral moves inward, bringing extra space down to O(1).

Approach 2: Layer-by-Layer (Boundary Shrinking)

Intuition

The spiral is a series of rectangular layers. The outermost layer is the border of the matrix. After traversing it, the remaining matrix is a smaller rectangle. We peel off one layer at a time, moving inward.

Four boundary variables, top, bottom, left, and right, mark the unvisited region. Each layer is traced with four sweeps:

  1. Traverse the top row from left to right, then move top down.
  2. Traverse the right column from top to bottom, then move right left.
  3. Traverse the bottom row from right to left (if rows remain), then move bottom up.
  4. Traverse the left column from bottom to top (if columns remain), then move left right.

The "if" checks on steps 3 and 4 are what keep single-row and single-column layers correct. After moving top down, the top and bottom boundaries may have crossed, so there is no separate bottom row left to traverse. Without the top <= bottom guard, step 3 would re-add the row that step 1 already covered. The same reasoning applies to left <= right and step 4.

Algorithm

  1. Initialize top = 0, bottom = m - 1, left = 0, right = n - 1.
  2. While top <= bottom and left <= right:
    1. Traverse the top row: for col from left to right, add matrix[top][col]. Increment top.
    2. Traverse the right column: for row from top to bottom, add matrix[row][right]. Decrement right.
    3. If top <= bottom: traverse the bottom row from right to left, add matrix[bottom][col]. Decrement bottom.
    4. If left <= right: traverse the left column from bottom to top, add matrix[row][left]. Increment left.
  3. Return the result list.

Example Walkthrough

Trace the 3x4 matrix:

Start with top=0, bottom=2, left=0, right=3.

The result is [1,2,3,4,8,12,11,10,9,5,6,7]. Layer 2 is where the guards matter: after the inner top row sets top=2, both the right-column and bottom-row sweeps cover empty ranges, so no element is added twice.

Code