Approach Summary
Track four boundaries (top, bottom, left, right). Traverse and shrink boundaries layer by layer.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Simulation with Visited Matrix | O(M * N) | O(M * N) | Simulates movement in a spiral using direction vectors [dr, dc] and a boolean visited array, turning right when a boundary or visited cell is reached. |
| 2 Approach 2: Four Boundary Pointers (Optimal) | O(M * N) | O(1) | Maintains top, bottom, left, and right boundary pointers that contract inward after each edge traversal, achieving O(1) auxiliary space. |
Step 1: Baseline
Approach 1: Simulation with Visited Matrix
Time: O(M * N)
Space: O(M * N)
1. Initialize an M x N boolean `visited` matrix. 2. Maintain current position (r, c) starting at (0, 0) and direction index `di = 0`. 3. Directions: `[(0, 1), (1, 0), (0, -1), (-1, 0)]` (right, down, left, up). 4. For step 0 to M*N - 1: - Append `matrix[r][c]` to result and mark `visited[r][c] = true`. - Calculate next cell `(nr, nc) = (r + dr, c + dc)`. - If `(nr, nc)` is out of bounds or already visited, increment `di = (di + 1) % 4`. - Move to new `(r + dr, c + dc)`. 5. Takes O(M * N) extra space for visited table.
Approach 1: Simulation with Visited Matrix Implementation
Approach 1: Simulation with Visited Matrix
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix.length == 0) return res;
int m = matrix.length, n = matrix[0].length;
boolean[][] vis = new boolean[m][n];
int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int r = 0, c = 0, di = 0;
for (int step = 0; step < m * n; step++) {
res.add(matrix[r][c]);
vis[r][c] = true;
int nr = r + dirs[di][0], nc = c + dirs[di][1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !vis[nr][nc]) {
r = nr; c = nc;
} else {
di = (di + 1) % 4;
r += dirs[di][0]; c += dirs[di][1];
}
}
return res;
}
}class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
if (matrix.empty()) return res;
int m = matrix.size(), n = matrix[0].size();
vector<vector<bool>> vis(m, vector<bool>(n, false));
int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int r = 0, c = 0, di = 0;
for (int step = 0; step < m * n; step++) {
res.push_back(matrix[r][c]);
vis[r][c] = true;
int nr = r + dirs[di][0], nc = c + dirs[di][1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !vis[nr][nc]) {
r = nr; c = nc;
} else {
di = (di + 1) % 4;
r += dirs[di][0]; c += dirs[di][1];
}
}
return res;
}
};class Solution:
def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
if not matrix: return []
m, n = len(matrix), len(matrix[0])
visited = [[False] * n for _ in range(m)]
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
r = c = di = 0
res = []
for _ in range(m * n):
res.append(matrix[r][c])
visited[r][c] = True
nr, nc = r + dirs[di][0], c + dirs[di][1]
if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
r, c = nr, nc
else:
di = (di + 1) % 4
r, c = r + dirs[di][0], c + dirs[di][1]
return resvar spiralOrder = function(matrix) {
if (!matrix.length) return [];
const m = matrix.length, n = matrix[0].length;
const visited = Array.from({length: m}, () => new Array(n).fill(false));
const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
let r = 0, c = 0, di = 0;
const res = [];
for (let step = 0; step < m * n; step++) {
res.push(matrix[r][c]);
visited[r][c] = true;
const nr = r + dirs[di][0], nc = c + dirs[di][1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
r = nr; c = nc;
} else {
di = (di + 1) % 4;
r += dirs[di][0]; c += dirs[di][1];
}
}
return res;
}; Step 2: Most Optimized
Approach 2: Four Boundary Pointers (Optimal)
Time: O(M * N)
Space: O(1)
1. Initialize `top = 0, bottom = m - 1, left = 0, right = n - 1`. 2. Loop while `top <= bottom && left <= right`: - Traverse row `top` from `left` to `right`, then `top++`. - Traverse column `right` from `top` to `bottom`, then `right--`. - If `top <= bottom`: traverse row `bottom` from `right` down to `left`, then `bottom--`. - If `left <= right`: traverse column `left` from `bottom` up to `top`, then `left++`. 3. Returns all elements in exact spiral sequence with zero extra memory allocated.
Approach 2: Four Boundary Pointers (Optimal) Implementation
Approach 2: Four Boundary Pointers (Optimal)
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) res.add(matrix[top][j]);
top++;
for (int i = top; i <= bottom; i++) res.add(matrix[i][right]);
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) res.add(matrix[bottom][j]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) res.add(matrix[i][left]);
left++;
}
}
return res;
}
}class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
int top = 0, bottom = matrix.size() - 1, left = 0, right = matrix[0].size() - 1;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) res.push_back(matrix[top][j]);
top++;
for (int i = top; i <= bottom; i++) res.push_back(matrix[i][right]);
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) res.push_back(matrix[bottom][j]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) res.push_back(matrix[i][left]);
left++;
}
}
return res;
}
};class Solution:
def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
res = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for j in range(left, right + 1): res.append(matrix[top][j])
top += 1
for i in range(top, bottom + 1): res.append(matrix[i][right])
right -= 1
if top <= bottom:
for j in range(right, left - 1, -1): res.append(matrix[bottom][j])
bottom -= 1
if left <= right:
for i in range(bottom, top - 1, -1): res.append(matrix[i][left])
left += 1
return resvar spiralOrder = function(matrix) {
const res = [];
let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (let j = left; j <= right; j++) res.push(matrix[top][j]);
top++;
for (let i = top; i <= bottom; i++) res.push(matrix[i][right]);
right--;
if (top <= bottom) {
for (let j = right; j >= left; j--) res.push(matrix[bottom][j]);
bottom--;
}
if (left <= right) {
for (let i = bottom; i >= top; i--) res.push(matrix[i][left]);
left++;
}
}
return res;
};Edge Cases to Watch
- Single row matrix [[1, 2, 3, 4]] — traverses left to right and terminates without attempting reverse direction
- Single column matrix [[1], [2], [3], [4]] — traverses top to bottom and terminates
- Square matrix (e.g. 3x3 or 4x4) — cleanly spirals to center element
- Empty matrix or matrix with 0 columns — returns empty array []
Algorithmic Pattern
View Pattern Guide →
Master the Matrix Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Matrix pattern.
How to Recognize This Pattern
- Spiral order traversal
- Layer-by-layer boundary shrinking
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(1)
Tags
Array Matrix Simulation
Frequently Asked Questions
What is the optimal time and space complexity for Spiral Matrix?
The optimal solution for Spiral Matrix achieves O(m × n) runtime complexity and requires O(1) auxiliary space. Time Complexity is O(M * N) where M is the number of rows and N is the number of columns, because every cell is visited and added to the output list exactly once. Space Complexity is O(1) auxiliary space (excluding the output array that stores the spiral elements).
How do I identify that Spiral Matrix requires the Matrix pattern?
In technical interviews, look for key problem signals: Spiral order traversal; Layer-by-layer boundary shrinking. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Matrix strategy.
What critical edge cases must be handled in Spiral Matrix?
Essential edge cases to verify include: Single row matrix [[1, 2, 3, 4]] — traverses left to right and terminates without attempting reverse direction; Single column matrix [[1], [2], [3], [4]] — traverses top to bottom and terminates; Square matrix (e.g. 3x3 or 4x4) — cleanly spirals to center element; Empty matrix or matrix with 0 columns — returns empty array []. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Spiral Matrix?
Spiral Matrix is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Microsoft, Apple, Google.