LeetCode 54 · Medium · Math & Geometry

Spiral Matrix

Read every value of an m × n matrix in clockwise spiral order: along the top row, down the right column, back along the bottom, up the left, then the next ring inside.

O(m · n)time
O(1)extra space
4 wallsshrink after each side

rows separated by ; and values by commas · 1–6 rows of 1–6 values, all rows the same length · integers −99 to 999

res

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

Why it works

  1. Simulation with a visited grid also works: walk, turn right when the next cell is outside or seen. O(m · n) time, but O(m · n) extra space for the visited marks.
  2. Four walls replace the visited grid: the outlined box is everything not yet read. Reading a full side moves that wall inward by one (top++ after the top row, right-- after the right column, and so on), so the box always holds exactly the unread cells.
  3. Each cell is added once: O(m · n) time, and four integers of extra space besides the output.
  4. Pitfall: the middle check. After the top row and right column, a single remaining row or column would be read twice on the way back. if (!(left < right && top < bottom)) break; stops that; try the one-row and 5×3 presets.
  5. Ranges are half-open: right and bottom point one past the last unread column and row, which is why the code reads right − 1 and bottom − 1.
  6. Related: Spiral Matrix II fills 1 to n² in the same order; Rotate Image works on the same rings.