Spiral Matrix III solution and explanation
Google
9 more videos on this problem
Spiral Matrix III | Simple Simulation | Made Easy | Leetcode 885 | codestorywithMIKcodestorywithMIK · 30:57 · 15K views
LeetCode 885: Spiral Matrix III - Interview Prep Ep 33Fisher Coder · 25:57 · 10K views
885. Spiral Matrix III | matrix | Leetcode Daily Challenge | DSA | HindiShashCode · 16:32 · 7K views
885. Spiral Matrix III (Leetcode Medium)Programming Live with Larry · 17:13 · 4K views
LeetCode | 885 Spiral Matrix III | Python3 | Explanationygongcode · 9:57 · 3K views
885. Spiral Matrix III | LeetCode Medium | Python Solution | Array, Matrix, SimulationShaheer Keerirakath · 3:36 · 2K views
Spiral Matrix III (LeetCode 885) (Easily Explained)CodeWithARB · 25:01 · 1K views
Facebook Coding Interview Question | Leetcode 885 | Spiral Matrix IIIWorkWithGoogler · 7:09 · 1K views
885. Spiral Matrix III - English VersionSimple Code - 단순코드 · 15:28 · 900 views
885 Spiral Matrix III | Leetcode Daily Challenge | Matrix | Java SolutionCakot Coding · 14:16 · 538 views
The problem
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 < 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.
def spiralMatrixIII(R, C, r0, c0):
res = [(r0, c0)]
steps = 1
# Directions: right, down, left, up
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while len(res) < R * C:
for i in range(4):
if i == 0 or i == 2:
for _ in range(steps):
r0 += directions[i][0]
c0 += directions[i][1]
if 0 <= r0 < R and 0 <= c0 < C:
res.append((r0, c0))
else:
for _ in range(steps):
r0 += directions[i][0]
c0 += directions[i][1]
if 0 <= r0 < R and 0 <= c0 < C:
res.append((r0, c0))
steps += 1
return resimport java.util.ArrayList;
import java.util.List;
class Solution {
public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
int[][] result = new int[rows * cols][2];
int[] dr = {0, 1, 0, -1};
int[] dc = {1, 0, -1, 0};
int x = rStart, y = cStart, steps = 0, dir = 0, k = 0;
result[k++] = new int[]{x, y};
while (k < rows * cols) {
if (dir == 0 || dir == 2) steps++;
for (int j = 0; j < steps; j++) {
x += dr[dir];
y += dc[dir];
if (x >= 0 && x < rows && y >= 0 && y < cols) {
result[k++] = new int[]{x, y};
}
}
dir = (dir + 1) % 4;
}
return result;
}
}#include <vector>
using namespace std;
vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
vector<vector<int>> result;
result.push_back({rStart, cStart});
int numSteps = 1;
while (result.size() < rows * cols) {
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < numSteps; ++j) {
if (result.size() == rows * cols) return result;
if (i == 0) cStart++;
if (i == 1) rStart++;
if (rStart >= 0 && rStart < rows && cStart >= 0 && cStart < cols) {
result.push_back({rStart, cStart});
}
}
}
numSteps++;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < numSteps; ++j) {
if (result.size() == rows * cols) return result;
if (i == 0) cStart--;
if (i == 1) rStart--;
if (rStart >= 0 && rStart < rows && cStart >= 0 && cStart < cols) {
result.push_back({rStart, cStart});
}
}
}
numSteps++;
}
return result;
}var spiralMatrixIII = function(rows, cols, rStart, cStart) {
const result = [];
let x = rStart, y = cStart, steps = 1, dir = 0;
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
result.push([x, y]);
while (result.length < rows * cols) {
if (dir % 2 === 0) {
for (let i = 0; i < steps; i++) {
x += directions[dir][0];
y += directions[dir][1];
if (x >= 0 && x < rows && y >= 0 && y < cols) {
result.push([x, y]);
}
}
} else {
for (let i = 0; i < steps; i++) {
x += directions[dir][0];
y += directions[dir][1];
if (x >= 0 && x < rows && y >= 0 && y < cols) {
result.push([x, y]);
}
}
steps++;
}
dir = (dir + 1) % 4;
}
return result;
};#include <stdio.h>
#include <stdlib.h>
int** spiralMatrixIII(int rows, int cols, int rStart, int cStart, int* returnSize, int** returnColumnSizes) {
*returnSize = rows * cols;
*returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
for (int i = 0; i < *returnSize; ++i) (*returnColumnSizes)[i] = 2;
int** result = (int**)malloc(sizeof(int*) * (*returnSize));
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // right, down, left, up
int totalSteps = 0, steps = 1;
int dir = 0;
result[totalSteps++] = (int*)malloc(sizeof(int) * 2);
result[0][0] = rStart; result[0][1] = cStart;
int r = rStart, c = cStart;
while (totalSteps < (*returnSize)) {
for (int i = 0; i < steps; ++i) {
r += directions[dir][0];
c += directions[dir][1];
if (0 <= r && r < rows && 0 <= c && c < cols) {
result[totalSteps] = (int*)malloc(sizeof(int) * 2);
result[totalSteps][0] = r;
result[totalSteps][1] = c;
totalSteps++;
}
}
if (dir == 1 || dir == 3) steps++;
dir = (dir + 1) % 4;
}
return result;
}public class Solution {
public int[][] SpiralMatrixIII(int rows, int cols, int rStart, int cStart) {
int[][] result = new int[rows * cols][];
int[] dr = new int[] {0, 1, 0, -1};
int[] dc = new int[] {1, 0, -1, 0};
int x = rStart, y = cStart, steps = 0, dir = 0, k = 0;
result[k++] = new int[]{x, y};
while (k < rows * cols) {
if (dir == 0 || dir == 2) steps++;
for (int j = 0; j < steps; j++) {
x += dr[dir];
y += dc[dir];
if (x >= 0 && x < rows && y >= 0 && y < cols) {
result[k++] = new int[]{x, y};
}
}
dir = (dir + 1) % 4;
}
return result;
}
}This Python solution uses direction vectors to simulate movement in a grid. Each directional change is associated with appropriate step increments.
Time Complexity: O(rows * cols), since each cell is visited once,
Space Complexity: O(rows * cols), for the result storage.
Approach 2: Default Approach
function spiralMatrixIII(rows: number, cols: number, rStart: number, cStart: number): number[][] {
// prettier-ignore
const dir = [[1,0],[0,1],[-1,0],[0,-1]]
let [x, y, i, size] = [cStart, rStart, 0, 0];
const ans: number[][] = [[y, x]];
const total = rows * cols;
while (ans.length < total) {
if (i % 2 === 0) size++;
for (let j = 0; ans.length < total && j < size; j++) {
x += dir[i][0];
y += dir[i][1];
if (0 <= x && x < cols && 0 <= y && y < rows) {
ans.push([y, x]);
}
}
i = (i + 1) % 4;
}
return ans;
}func spiralMatrixIII(rows int, cols int, rStart int, cStart int) [][]int {
cnt := rows * cols
ans := [][]int{[]int{rStart, cStart}}
if cnt == 1 {
return ans
}
for k := 1; ; k += 2 {
dirs := [][]int{{0, 1, k}, {1, 0, k}, {0, -1, k + 1}, {-1, 0, k + 1}}
for _, dir := range dirs {
r, c, dk := dir[0], dir[1], dir[2]
for dk > 0 {
rStart += r
cStart += c
if rStart >= 0 && rStart < rows && cStart >= 0 && cStart < cols {
ans = append(ans, []int{rStart, cStart})
if len(ans) == cnt {
return ans
}
}
dk--
}
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simulate the Spiral Path | Time Complexity: O(rows * cols), since each cell is visited once, |
| Default Approach | – |
Complexity analysis
| 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 |
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.