Spiral Matrix

Problem in Plain English

Collect every element of an m x n matrix in clockwise spiral order, starting at the top-left corner and winding inward layer by layer.

Problem Statement

Given an m x n matrix, return all of its elements in spiral order: start at the top-left corner, walk right across the top row, down the right column, left across the bottom row, and up the left column, then repeat one layer deeper until every cell is collected.

Single rows, single columns, and non-square shapes all spiral the same way; the walk simply stops when the boundaries cross.

Constraints

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

Examples

Example 1

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

Walk right through [1, 2, 3], down through [6, 9], left through [8, 7], and up through [4]. The only unvisited cell is the center 5, which completes the result.

Example 2

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]

The outer lap collects ten cells, leaving the inner row segment [6, 7].

Example 3

Input: matrix = [[-100, 0, 100]]
Output: [-100, 0, 100]

There is only one row, so the initial rightward pass collects every cell. The bottom-row pass must be skipped instead of appending the same values again. Values do not determine when the walk turns.

Example 4

Input: matrix = [[1], [2], [3]]
Output: [1, 2, 3]

The top-row pass collects 1, then the right-column pass collects 2 and 3. There is no separate left column left to visit, so the upward pass is skipped.

Intuition

A spiral peels the outside of a rectangle before entering the next rectangle. In Example 1, the perimeter gives [1, 2, 3, 6, 9, 8, 7, 4], then the center gives 5. You can remember each visited position and turn right when the next cell is blocked. Because the remaining cells always form an inner rectangle, four boundary indices can replace that entire visited grid. Shrink each boundary after walking its side, and guard the return sides when a thin rectangle has already been consumed.

Approaches

Visited Simulation

Solution Details

Reveal Visited Simulation: intuition, complexity, and code

Intuition

Walking the spiral is just moving straight until something blocks the way, then turning right: a wall, the matrix edge, or an already collected cell. A visited grid remembers collected cells, and a four-direction compass cycles right, down, left, up.

Step-by-Step Logic

Allocate an m by n visited grid and an empty result. Start at (r, c) = (0, 0) with dir = 0; direction indices 0, 1, 2, 3 mean right, down, left, up. Example 1 has m = n = 3.
On each of exactly m times n iterations, append matrix[r][c] and mark that position visited. In Example 1 the first three appends are 1, 2, 3 across the top row.
If that append fills the result, stop before computing a next position. Otherwise try (r + dr[dir], c + dc[dir]); check its bounds before reading its visited flag.
When the candidate is outside the matrix or already visited, turn right with dir = (dir + 1) % 4 and recompute it. Example 1 turns down after 3, left after 9, up after 7, and right after 4 because (0, 0) is visited.
Move to the chosen candidate and repeat. Example 1 enters (1, 1), appends 5 as the ninth cell, and returns [1, 2, 3, 6, 9, 8, 7, 4, 5] without altering the matrix.

Why It Works

Before each iteration, (r, c) is the next unvisited cell in a clockwise perimeter walk, and visited marks exactly the cells already appended. Appending then marking includes that cell once. Moving straight follows the current side; when the edge or a visited cell blocks it, a right turn follows the next side of the unvisited rectangle. Completing a perimeter brings the walk to the next inner perimeter. As long as cells remain, that right-turn destination is unvisited; after the final append, the explicit stop avoids attempting another move. Exactly m times n iterations therefore collect all positions in spiral order, including thin rectangles, without relying on distinct values.

Dry Run

Visited Simulation: variable states at each step
i	r, c before	appended	direction before → after	straight candidate	decision	next r, c	visited rows after (1 = seen)	result after
0	(0, 0)	1	right → right	(0, 1)	unvisited: straight	(0, 1)	100/000/000	[1]
1	(0, 1)	2	right → right	(0, 2)	unvisited: straight	(0, 2)	110/000/000	[1,2]
2	(0, 2)	3	right → down	(0, 3)	outside: turn right	(1, 2)	111/000/000	[1,2,3]
3	(1, 2)	6	down → down	(2, 2)	unvisited: straight	(2, 2)	111/001/000	[1,2,3,6]
4	(2, 2)	9	down → left	(3, 2)	outside: turn right	(2, 1)	111/001/001	[1,2,3,6,9]
5	(2, 1)	8	left → left	(2, 0)	unvisited: straight	(2, 0)	111/001/011	[1,2,3,6,9,8]
6	(2, 0)	7	left → up	(2, -1)	outside: turn right	(1, 0)	111/001/111	[1,2,3,6,9,8,7]
7	(1, 0)	4	up → right	(0, 0)	visited: turn right	(1, 1)	111/101/111	[1,2,3,6,9,8,7,4]
8	(1, 1)	5	right	stop	all 9 cells collected	—	111/111/111	[1,2,3,6,9,8,7,4,5]

Complexity Analysis

Time Complexity

O(m \times n)

Space Complexity

O(m \times n)

Let m and n be the row and column counts. Each of the m times n cells is appended and marked once; each iteration makes at most one direction change, so traversal and visited-grid initialization take O(m times n) time. The visited grid stores m times n flags plus m row containers, giving O(m times n) auxiliary space. The newly allocated result also stores m times n values/references; direction arrays have constant size. Dynamic result growth is amortized linear and does not change the bound. Input values and row identities are preserved.

Code

Solution.java

1import java.util.ArrayList;2import java.util.List;3
4class Solution {5    public List<Integer> spiralOrder(int[][] matrix) {6        List<Integer> res = new ArrayList<>();7        int m = matrix.length;8        int n = matrix[0].length;9        boolean[][] visited = new boolean[m][n];10        int[] dr = {0, 1, 0, -1};11        int[] dc = {1, 0, -1, 0};12        int r = 0, c = 0, dir = 0;13        for (int i = 0; i < m * n; i++) {14            res.add(matrix[r][c]);15            visited[r][c] = true;16            // No next position exists after the final cell, especially for thin grids.17            if (i == m * n - 1) break;18            int nr = r + dr[dir];19            int nc = c + dc[dir];20            // Short-circuit bounds before indexing visited; blocked movement turns clockwise.21            if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) {22                dir = (dir + 1) % 4;23                nr = r + dr[dir];24                nc = c + dc[dir];25            }26            r = nr;27            c = nc;28        }29        return res;30    }31}

Hints

Hint 1

Trace Example 1 by hand and mark when the walk turns: each turn happens at an edge or an already collected cell.

Hint 2

Simulate with a facing direction plus a visited grid, or fence the unvisited rectangle with four walls and walk it lap by lap.

Hint 3

After each side, pull its wall inward, and re-check that the walls have not crossed before walking the bottom row or left column: single rows and columns skip those sides.

Edge Cases

A 1 by 1 matrix returns its one value; the simulation stops before trying another move.
A single row such as Example 3 is collected entirely by the top pass. The right and left ranges are empty, and the bottom guard fails.
A single column such as Example 4 is collected by the top and right passes. The bottom range is empty, and the left guard fails.
A non-square inner layer can be a row segment, as in Example 2, or a column segment such as a 4 by 3 matrix. Crossing guards apply on every lap.
Duplicate values, zeros, negatives and extrema are ordinary data. Track positions rather than using values as visited markers.

Common Mistakes and Interview Tips

Walking bottom and left unconditionally duplicates positions when an inner layer is a single row or column. Re-check the corresponding bounds after the earlier sides shrink.
Moving a boundary before traversing its own side skips that side. Shrink it after collection but before walking the adjacent side.
Using strict inequalities for inclusive wall ranges skips endpoints. Use inclusive traversal bounds and both non-crossed pairs for the outer while condition.
Using a shared visited row, such as Python [[False] * n] * m or JavaScript fill(new Array(n)), aliases flags across rows. Allocate each visited row separately.
Treating repeated values as already visited loses cells. The simulation stores coordinate flags and marks each cell immediately after appending.
Interview tip: distinguish O(1) auxiliary boundary storage from the mandatory O(m times n) output. Explain the two crossing guards using both one-row and one-column examples.

Key Takeaway

Fencing the unvisited region with moving walls turns fiddly grid walks into four straight loops plus crossing checks.