Spiral Matrix

You are given a rectangular grid of integers matrix with m rows and n columns.

Walk the grid in a clockwise spiral and return every value in the order you visit it. Start at the top-left cell and move right along the top row, then down the right column, then left along the bottom row, then up the left column. Then step one ring inward and repeat, until every cell has been visited exactly once.

The grid does not have to be square, so the innermost part may be a single row, a single column or a single cell.

Example 1

Example 2

Example 3

Constraints

• m == matrix.length, n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

Pattern Path · Math, Bits & Strings · problem 38 of 169

Start simple

Simulate a walker that turns right whenever the next cell is outside the grid or already visited, using an m×n visited array: O(mn) time and O(mn) extra space.

The key idea

Track the unvisited part of the grid as a shrinking rectangle with four boundaries: top, bottom, left, right. One loop iteration peels off its outer ring:

• read the top row from left to right, then top += 1;
• read the right column from top to bottom, then right -= 1;
• if a row is still left, read the bottom row from right back to left, then bottom -= 1;
• if a column is still left, read the left column from bottom up to top, then left += 1.

The two guarded passes are the subtle part. After the first two passes the rectangle may have collapsed to zero rows or zero columns (for example, in a 1×4 or 4×1 grid, or the middle row of a 3×5 grid). Without the checks, the walk would go back over cells it has already output.

Every cell is output exactly once and no visited array is needed.

Complexity

• Time: O(m·n)
• Space: O(1) besides the output

Python

class Solution:
    def spiralOrder(self, matrix):
        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):          # top row, left to right
                result.append(matrix[top][c])
            top += 1
            for r in range(top, bottom + 1):          # right column, downwards
                result.append(matrix[r][right])
            right -= 1
            if top <= bottom:                         # bottom row, right to left
                for c in range(right, left - 1, -1):
                    result.append(matrix[bottom][c])
                bottom -= 1
            if left <= right:                         # left column, upwards
                for r in range(bottom, top - 1, -1):
                    result.append(matrix[r][left])
                left += 1
        return result

JavaScript

var spiralOrder = function(matrix) {
  const result = [];
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c++) result.push(matrix[top][c]);     // top row
    top++;
    for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);   // right column
    right--;
    if (top <= bottom) {                                                  // bottom row
      for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);
      bottom--;
    }
    if (left <= right) {                                                  // left column
      for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);
      left++;
    }
  }
  return result;
};

What the interviewer is checking

This is a careful-implementation question: the interviewer watches how you manage boundaries and whether you test single-row and single-column cases before declaring victory.

Mistakes to avoid

• Revisiting cells when the last remaining area is a single row or column.
• Off-by-one errors in the reverse loops (right to left, bottom to top).
• Assuming the grid is square.

Follow-ups to expect

• Fill an n×n grid with 1..n² in spiral order. (Same boundaries, write instead of read.)
• Return the spiral counter-clockwise or from a given start cell. (Change pass order or direction table.)
• Can you do it with a direction vector instead of four loops? (Turn when blocked, track visited.)

In real software

Spiral and ring traversals show up in image processing (peeling borders), LED panel animations and search patterns that expand outward from a point on a grid map.

Practice next