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).
To simulate walking in a spiral, maintain a direction vector and a step count for each segment. Initially face east, and keep track of direction changes in the order of east, south, west, north. After two direction changes, increase the step count which determines how far to walk in the current direction before turning.
This solution initializes variables for direction and position, and iterates until all grid elements are visited. For each direction, it moves step-by-step and checks boundary conditions to ensure valid indices.
Time Complexity: O(rows * cols), since each cell is visited once,
Space Complexity: O(rows * cols), for the result storage.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Simulate the Spiral Path | Time Complexity: O(rows * cols), since each cell is visited once, |
| Default Approach | — |
| 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 |
Spiral Matrix III - Leetcode 885 - Python • NeetCodeIO • 16,444 views views
Watch 9 more video solutions →Practice Spiral Matrix III with our built-in code editor and test cases.
Practice on FleetCode