Watch 10 video solutions for Spiral Matrix III, a medium level problem involving Array, Matrix, Simulation. This walkthrough by NeetCodeIO has 16,444 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You start at the cell (rStart, cStart) of an rows x cols grid facing east. The northwest corner is at the first row and column in the grid, and the southeast corner is at the last row and column.
You will walk in a clockwise spiral shape to visit every position in this grid. Whenever you move outside the grid's boundary, we continue our walk outside the grid (but may return to the grid boundary later.). Eventually, we reach all rows * cols spaces of the grid.
Return an array of coordinates representing the positions of the grid in the order you visited them.
Example 1:
Input: rows = 1, cols = 4, rStart = 0, cStart = 0 Output: [[0,0],[0,1],[0,2],[0,3]]
Example 2:
Input: rows = 5, cols = 6, rStart = 1, cStart = 4 Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]
Constraints:
1 <= rows, cols <= 1000 <= rStart < rows0 <= cStart < colsProblem Overview: You start at position (rStart, cStart) in a rows x cols grid and move in a spiral pattern: right, down, left, up, expanding outward. The task is to return the coordinates of every cell in the grid in the exact order they are visited. The spiral may temporarily go outside the grid, but you only record coordinates that fall inside the valid matrix.
Approach 1: Visited Grid Simulation (O((rows*cols)^2) time, O(rows*cols) space)
A straightforward idea is to simulate movement step by step while maintaining a visited matrix. Continue turning right whenever you hit a boundary or a visited cell. Each valid coordinate is appended to the result list until all rows * cols cells are collected. This works but wastes time because the spiral can travel outside the grid and revisit boundary checks repeatedly. The extra visited matrix also increases memory usage. Useful mainly for understanding spiral traversal mechanics in matrix problems.
Approach 2: Expanding Spiral Path Simulation (O(rows*cols) time, O(1) space)
The efficient solution directly models the spiral pattern. Movement follows four directions in order: right, down, left, up. The key observation: the step length increases after every two directions. For example: move 1 step right, 1 step down, 2 steps left, 2 steps up, 3 steps right, 3 steps down, and so on. During traversal, append a coordinate only if it lies within the grid bounds. The spiral may travel outside the grid, but eventually every valid cell is reached exactly once. This avoids maintaining a visited structure and keeps space constant. The approach relies on simple iteration and boundary checks, making it a common simulation pattern in array and simulation problems.
Recommended for interviews: The expanding spiral path simulation is the expected solution. Interviewers want to see that you recognize the pattern of increasing step lengths after every two directions. The brute simulation with a visited grid demonstrates basic traversal thinking, but the optimized spiral simulation shows stronger algorithmic insight and reduces space from O(rows*cols) to O(1).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Visited Grid Simulation | O((rows*cols)^2) | O(rows*cols) | Conceptual approach when first learning spiral traversal or debugging movement logic |
| Expanding Spiral Path Simulation | O(rows*cols) | O(1) | Optimal solution for interviews and production; minimal memory and predictable spiral movement |