Spiral Matrix

Approach Summary

Track four boundaries (top, bottom, left, right). Traverse and shrink boundaries layer by layer.

Full Solution & Approach

Walk the matrix in concentric layers, consuming the outermost ring first and moving inward. Keep four boundaries — top, bottom, left, right — that shrink after each edge of the current ring is fully consumed. Start at the top-left and move right across the top row, then down the right column, then left across the bottom row, then up the left column, appending every cell to the result. After finishing a ring, shrink all four boundaries by one and repeat until top passes bottom or left passes right. The subtle part is that after moving right and down, the remaining two edges may no longer exist if the ring collapsed to a single row or a single column — so the bottom-left and right-up traversals must each be guarded with a boundary check (top <= bottom and left <= right) to avoid double-visiting a degenerate row or column. The result visits every cell exactly once. This layered-boundary pattern is the standard answer and transfers directly to similar problems like generating a spiral matrix of a given size.

Each cell is appended exactly once across all rings — O(m × n) time for an m×n matrix. Only four boundary variables plus the output, so O(1) space beyond the result.

Solution Code

Solution

def spiral_order(matrix: list[list[int]]) -> list[int]:
    res = []
    if not matrix:
        return res
    top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for j in range(left, right + 1):
            res.append(matrix[top][j])
        top += 1
        for i in range(top, bottom + 1):
            res.append(matrix[i][right])
        right -= 1
        if top <= bottom:
            for j in range(right, left - 1, -1):
                res.append(matrix[bottom][j])
            bottom -= 1
        if left <= right:
            for i in range(bottom, top - 1, -1):
                res.append(matrix[i][left])
            left += 1
    return res

function spiralOrder(matrix) {
  const res = [];
  if (!matrix.length) return res;
  let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let j = left; j <= right; j++) res.push(matrix[top][j]);
    top++;
    for (let i = top; i <= bottom; i++) res.push(matrix[i][right]);
    right--;
    if (top <= bottom) {
      for (let j = right; j >= left; j--) res.push(matrix[bottom][j]);
      bottom--;
    }
    if (left <= right) {
      for (let i = bottom; i >= top; i--) res.push(matrix[i][left]);
      left++;
    }
  }
  return res;
}

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new ArrayList<>();
    if (matrix.length == 0) return res;
    int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) res.add(matrix[top][j]);
        top++;
        for (int i = top; i <= bottom; i++) res.add(matrix[i][right]);
        right--;
        if (top <= bottom) {
            for (int j = right; j >= left; j--) res.add(matrix[bottom][j]);
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) res.add(matrix[i][left]);
            left++;
        }
    }
    return res;
}

vector<int> spiralOrder(const vector<vector<int>>& matrix) {
    vector<int> res;
    if (matrix.empty()) return res;
    int top = 0, bottom = (int)matrix.size() - 1, left = 0, right = (int)matrix[0].size() - 1;
    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) res.push_back(matrix[top][j]);
        top++;
        for (int i = top; i <= bottom; i++) res.push_back(matrix[i][right]);
        right--;
        if (top <= bottom) {
            for (int j = right; j >= left; j--) res.push_back(matrix[bottom][j]);
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) res.push_back(matrix[i][left]);
            left++;
        }
    }
    return res;
}

Edge Cases to Watch

Empty matrix — return []
Single row — only the left-to-right pass runs; the guards prevent double traversal
Single column — only top-to-bottom runs
1×1 matrix — a single element

How to Recognize This Pattern

Spiral order traversal
Layer-by-layer boundary shrinking

Complexity Analysis

Time Complexity

O(m × n)

Space Complexity

O(1)