Spiral Matrix
Problem
m × n matrix, return all of its elements in
clockwise spiral order: start at the top-left, go right along the top row, down the
right column, left along the bottom row, up the left column, then repeat on the inner ring.[[1,2,3],[4,5,6],[7,8,9]]Output[1,2,3,6,9,8,7,4,5][[1,2,3,4],[5,6,7,8]]Output[1,2,3,4,8,7,6,5]1 ≤ m, n ≤ 10 · -100 ≤ matrix[i][j] ≤ 100
Try it yourself
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
}
}
top, bottom, left, right. After each side is walked, move that boundary inward;
stop when they cross.Instinct A 2D grid you must walk in a fixed geometric order (spiral, diagonal, layer, rotate) or update in place - think boundaries, direction vectors and index maths.
Memory hack Walk the walls, then shrink the room - four fences (top, bottom, left, right) close in after every lap.
Open the Matrix Traversal guide →Approaches
Brute ForceDirection Simulation + Visited Grid
O(m·n)Space O(m·n)Walk like a robot with direction vectors right → down → left → up.
Mark each cell in visited; if the next step leaves the grid or hits a visited
cell, turn clockwise. Exactly m·n steps.
public List<Integer> spiralOrder(int[][] matrix) { List<Integer> result = new ArrayList<>(); int m = matrix.length, n = matrix[0].length; boolean[][] visited = new boolean[m][n]; int[] dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0}; // right, down, left, up int r = 0, c = 0, d = 0; for (int k = 0; k < m * n; k++) { result.add(matrix[r][c]); visited[r][c] = true; int nr = r + dr[d], nc = c + dc[d]; if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) { d = (d + 1) % 4; // blocked: turn clockwise nr = r + dr[d]; nc = c + dc[d]; } r = nr; c = nc; } return result; }
Hard to get wrong, but needs an extra m×n boolean grid.
OptimalLayer-by-Layer Boundaries
O(m·n)Space O(1)Walk the top row, then top++; the right column, then
right--; the bottom row, then bottom--; the left column, then
left++. The bottom/left walks are guarded by top ≤ bottom /
left ≤ right so a single remaining row or column is not read twice.
(Space excludes the output list.)
public List<Integer> spiralOrder(int[][] matrix) { List<Integer> result = new ArrayList<>(); int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1; while (top <= bottom && left <= right) { for (int i = left; i <= right; i++) result.add(matrix[top][i]); top++; for (int i = top; i <= bottom; i++) result.add(matrix[i][right]); right--; if (top <= bottom) { // a bottom row still remains for (int i = right; i >= left; i--) result.add(matrix[bottom][i]); bottom--; } if (left <= right) { // a left column still remains for (int i = bottom; i >= top; i--) result.add(matrix[i][left]); left++; } } return result; }
Same time, no visited grid — the standard interview answer.
[[1,2,3]] and a single
column [[1],[2],[3]] expose missing guards immediately.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Direction Simulation + Visited Grid | O(m·n) | O(m·n) |
| Optimal | Layer-by-Layer Boundaries | O(m·n) | O(1) |
- Dropping the
top ≤ bottom/left ≤ rightguards — duplicates on non-square input. - Turning on the visited check but forgetting the bounds check (or vice versa).
- Swapping row/column indices —
matrix[row][col], rows =matrix.length.
- Draw the four boundaries and say which one moves after each side.
- Mention the follow-on: Spiral Matrix II fills the same path with 1..n2.
- Prove termination: each full lap removes at least one row or column.