Skip to main content
Talentd

Spiral Matrix III - Solution & Explanation

MediumArrayMatrixSimulation11 min readAsked at: Amazon, Microsoft, Apple +5
Practice this problem

Problem Statement

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 <= 100
  • 0 <= rStart < rows
  • 0 <= cStart < cols

Approach Overview

Problem 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 1: Simulate the Spiral Path

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(rows * cols), since each cell is visited once,
Space Complexity: O(rows * cols), for the result storage.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Simulate the Spiral Path

Time Complexity: O(rows * cols), since each cell is visited once,
Space Complexity: O(rows * cols), for the result storage.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Visited Grid SimulationO((rows*cols)^2)O(rows*cols)Conceptual approach when first learning spiral traversal or debugging movement logic
Expanding Spiral Path SimulationO(rows*cols)O(1)Optimal solution for interviews and production; minimal memory and predictable spiral movement

Video Solution

Spiral Matrix III | Simple Simulation | Made Easy | Leetcode 885 | codestorywithMIK • codestorywithMIK • 15,868 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Spiral Matrix III easy or hard?
Spiral Matrix III is rated Medium because the logic for expanding spiral steps can be tricky at first. Once you recognize the pattern of increasing step lengths after every two directions, the implementation becomes straightforward.
Spiral Matrix III Python/Java solution
Both Python and Java implementations follow the same spiral simulation logic. Maintain direction vectors, track the current step length, and expand it after every two turns. Append coordinates to the result only when they fall within the grid bounds.
How to solve Spiral Matrix III in O(n)?
Treat n as the total number of cells (rows * cols). Simulate the spiral using a direction array and increase the step length after every two directions. During each step, check whether the current position lies inside the grid before adding it to the result list.
What is the best approach for Spiral Matrix III?
The best approach is spiral path simulation with expanding step lengths. Move in four directions (right, down, left, up) and increase the step size after every two turns. Record coordinates only when they fall inside the grid. This visits all cells in O(rows*cols) time using O(1) extra space.
Is Spiral Matrix III asked at Google/Amazon/Meta?
Spiral traversal and matrix simulation problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants such as Spiral Matrix, Spiral Matrix II, and coordinate traversal questions test simulation logic and boundary handling.
What data structure is used in Spiral Matrix III?
The solution mainly uses arrays or lists to store the resulting coordinates and a small direction array to control movement. No advanced data structures are required; the core idea is controlled simulation over a matrix grid.
What is the time complexity of Spiral Matrix III?
The optimal solution runs in O(rows*cols) time because every valid cell in the grid is recorded exactly once. The spiral may step outside the grid temporarily, but the total useful operations remain proportional to the number of cells.

Ready to solve this problem?

Practice Spiral Matrix III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Spiral Matrix

Next

Spiral Matrix II