Spiral Matrix

Examples

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

Across the top (1,2,3), down the right side (6,9), across the bottom right-to-left (8,7), up the left side (4), then the single cell left in the middle (5).

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Input: matrix = [[1]]
Output: [1]

Constraints

• 1 <= m, n <= 10

• -100 <= matrix[i][j] <= 100

Approach

A direct way to simulate the spiral is to walk the grid one cell at a time, always moving in the current direction (right, down, left, or up) until the next step would go off the grid or onto an already-visited cell - at which point you turn 90 degrees and keep going. This mirrors exactly how you'd trace a spiral by hand, but it needs a separate "visited" grid to know when to turn.

A cleaner approach tracks four shrinking boundaries instead - the current top row, bottom row, left column, and right column of the region still left to visit. Sweep along each edge of that region in turn (top row left-to-right, right column top-to-bottom, bottom row right-to-left, left column bottom-to-top), and after each full sweep, shrink the corresponding boundary inward by one. Repeat until the boundaries cross, and every cell has been visited exactly once, with no extra "visited" grid required.

Solutions

Brute Force - Simulate With a Visited Grid

Walk the grid one step at a time in the current direction (starting by moving right). Whenever the next cell would be off the grid or already visited, turn 90 degrees clockwise instead. Keep a same-size grid of booleans to know which cells have already been recorded.

function spiralOrder(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // right, down, left, up
  const result = [];

  let r = 0, c = 0, dir = 0;

  for (let i = 0; i < rows * cols; i++) {
    result.push(matrix[r][c]);
    visited[r][c] = true;

    const [dr, dc] = directions[dir];
    let nr = r + dr;
    let nc = c + dc;

    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || visited[nr][nc]) {
      dir = (dir + 1) % 4;
      nr = r + directions[dir][0];
      nc = c + directions[dir][1];
    }

    r = nr;
    c = nc;
  }

  return result;
}

Time: O(m · n) · Space: O(m · n), for the visited grid

Optimal - Four Shrinking Boundaries

Track the top, bottom, left, and right edges of the region still left to visit. Sweep along the top row, then the right column, then the bottom row, then the left column - shrinking each boundary inward right after its sweep - and stop once the boundaries cross.

function spiralOrder(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++;

    for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);
    right--;

    if (top <= bottom) {
      for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);
      bottom--;
    }

    if (left <= right) {
      for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);
      left--;
    }
  }

  return result;
}

Time: O(m · n) · Space: O(1) extra space, beyond the output list