Spiral Matrix solution and explanation
Cisco
9 more videos on this problem
Spiral Traversal of a Matrix | Spiral Matrixtake U forward · 16:33 · 522K views
Spiral Matrix - Microsoft Interview Question - Leetcode 54NeetCode · 16:46 · 239K views
LeetCode Spiral Matrix Solution Explained - JavaNick White · 11:07 · 52K views
Spiral Matrix (LeetCode 54) | Full Solution with Visualizations | Study AlgorithmsNikhil Lohia · 13:27 · 51K views
Spiral Matrix - Leetcode 54 - Arrays & Strings (Python)Greg Hogg · 8:32 · 27K views
Spiral Matrix - LeetCode 54 - JavaScriptAlgoJS · 8:39 · 4K views
Spiral Matrix - LeetCode 54 - Python #blind75 #leetcode #spiralmatrixDeepti Talesra · 14:31 · 2K views
LeetCode 54: Spiral Matrix - Interview Prep Ep 31Fisher Coder · 16:56 · 2K views
LeetCode 54: Spiral Matrix | C# Solution | Matrix Traversal |Code Scribbler · 12:11 · 978 views
Spiral Matrix | LeetCode 54 (Medium)Destination FAANG · 19:31 · 859 views
The problem
Given an m x n matrix, return all elements of the matrix in spiral order.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
Approach overview
Problem Overview: Given an m × n matrix, return all elements in spiral order. The traversal starts at the top-left corner, moves right across the first row, then down the last column, then left across the bottom row, and continues inward layer by layer until every element is visited.
Approach 1: Iterative Boundary Management (O(m×n) time, O(1) space)
This approach simulates the spiral traversal by maintaining four boundaries: top, bottom, left, and right. You iterate across the top row, then move down the right column, then traverse the bottom row in reverse, and finally move up the left column. After completing each direction, adjust the corresponding boundary inward. The key insight is that every spiral layer shrinks the valid traversal region. Each matrix element is visited exactly once, giving O(m×n) time with constant extra space. This method fits naturally with problems involving array traversal and matrix boundary processing.
Approach 2: Recursive Divide and Conquer (O(m×n) time, O(m+n) recursion space)
The matrix can also be processed layer by layer using recursion. Each recursive call handles one outer ring of the matrix: traverse the top row, right column, bottom row (reverse), and left column (reverse). After processing the outer layer, the recursion continues with the inner submatrix defined by updated boundaries. The recursive structure mirrors the spiral pattern directly, which can make the logic easier to reason about. The tradeoff is additional recursion stack usage proportional to the number of layers, typically O(min(m,n)). This approach is a natural fit when practicing simulation or divide-and-conquer thinking.
Recommended for interviews: Iterative boundary management is the expected solution. Interviewers want to see careful boundary updates and correct handling of edge cases when rows or columns collapse. The recursive version demonstrates conceptual clarity but rarely improves performance. Showing the iterative solution proves you can control indices precisely and implement efficient matrix traversal.
Approach 1: Iterative Boundary Management
This approach involves simulating the spiral order by iteratively traversing matrix layers. The boundaries are adjusted after each complete traversal of a side (top, right, bottom, left). By shrinking the boundaries, we can eventually cover the entire matrix in a spiral order.
def spiralOrder(matrix):
result = []
if not matrix:
return result
top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for i in range(left, right + 1):
result.append(matrix[top][i])
top += 1
for i in range(top, bottom + 1):
result.append(matrix[i][right])
right -= 1
if top <= bottom:
for i in range(right, left - 1, -1):
result.append(matrix[bottom][i])
bottom -= 1
if left <= right:
for i in range(bottom, top - 1, -1):
result.append(matrix[i][left])
left += 1
return resultimport java.util.ArrayList;
import java.util.List;
public class SpiralMatrix {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (int i = left; i <= right; i++) result.add(matrix[top][i]);
top++;
for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
right--;
if (top <= bottom) {
for (int i = right; i >= left; i--) result.add(matrix[bottom][i]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
left++;
}
}
return result;
}
}#include <vector>
using namespace std;
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> result;
int top = 0, bottom = matrix.size() - 1, left = 0, right = matrix[0].size() - 1;
while (top <= bottom && left <= right) {
for (int i = left; i <= right; ++i) result.push_back(matrix[top][i]);
top++;
for (int i = top; i <= bottom; ++i) result.push_back(matrix[i][right]);
right--;
if (top <= bottom) {
for (int i = right; i >= left; --i) result.push_back(matrix[bottom][i]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; --i) result.push_back(matrix[i][left]);
left++;
}
}
return result;
}var spiralOrder = function(matrix) {
let result = [];
let top = 0, bottom = matrix.length - 1;
let left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (let i = left; i <= right; i++) result.push(matrix[top][i]);
top++;
for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
right--;
if (top <= bottom) {
for (let i = right; i >= left; i--) result.push(matrix[bottom][i]);
bottom--;
}
if (left <= right) {
for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
left++;
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
int top = 0, bottom = matrixSize - 1, left = 0, right = matrixColSize[0] - 1;
int* result = (int*)malloc((matrixSize * matrixColSize[0]) * sizeof(int));
int k = 0;
while (top <= bottom && left <= right) {
for (int i = left; i <= right; ++i) result[k++] = matrix[top][i];
top++;
for (int i = top; i <= bottom; ++i) result[k++] = matrix[i][right];
right--;
if (top <= bottom) {
for (int i = right; i >= left; --i) result[k++] = matrix[bottom][i];
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; --i) result[k++] = matrix[i][left];
left++;
}
}
*returnSize = k;
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> SpiralOrder(int[][] matrix) {
var result = new List<int>();
int top = 0, bottom = matrix.Length - 1;
int left = 0, right = matrix[0].Length - 1;
while (top <= bottom && left <= right) {
for (int i = left; i <= right; i++) result.Add(matrix[top][i]);
top++;
for (int i = top; i <= bottom; i++) result.Add(matrix[i][right]);
right--;
if (top <= bottom) {
for (int i = right; i >= left; i--) result.Add(matrix[bottom][i]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) result.Add(matrix[i][left]);
left++;
}
}
return result;
}
}The Python solution uses lists and iterates over the given matrix using controlled loops defined by boundary variables. Each side's traversal is performed iteratively, ensuring the entire matrix is traversed in spiral form.
Time Complexity: O(m * n) where m is the number of rows and n is the number of columns.
Space Complexity: O(1) additional space, excluding the result list.
Approach 2: Recursive Divide and Conquer
This approach uses recursion to divide the matrix into smaller sections. By processing the outer layer of the matrix, we can recursively call the function on the remaining submatrix. This continues until the entire matrix is covered.
def spiralOrder(matrix):
result = []
if matrix:
def spiral_layer(top, bottom, left, right):
if top > bottom or left > right:
return
result.extend(matrix[top][i] for i in range(left, right + 1))
result.extend(matrix[i][right] for i in range(top + 1, bottom + 1))
if top < bottom:
result.extend(matrix[bottom][i] for i in range(right - 1, left - 1, -1))
if left < right:
result.extend(matrix[i][left] for i in range(bottom - 1, top, -1))
spiral_layer(top + 1, bottom - 1, left + 1, right - 1)
spiral_layer(0, len(matrix) - 1, 0, len(matrix[0]) - 1)
return resultThe Python solution defines a recursive helper function `spiral_layer`, with parameters defining the boundaries of the current submatrix. The base condition checks if the boundary indices are valid. It extracts and appends elements to the result, then recursively narrows the boundaries until they converge.
Time Complexity: O(m * n) since each recursive call processes an entire layer of the matrix.
Space Complexity: O(m * n) due to the recursive call stack usage, although tail recursion may optimize this depending on the Python implementation.
Approach 3: Simulation
We can simulate the entire traversal process. We use i and j to represent the row and column of the current element being visited, and k to represent the current direction. We use an array or hash table vis to record whether each element has been visited. Each time we visit an element, we mark it as visited, then move one step forward in the current direction. If moving forward results in an out-of-bounds condition or the element has already been visited, we change direction and continue moving forward until the entire matrix has been traversed.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the matrix, respectively.
function spiralOrder(matrix: number[][]): number[] {
const m = matrix.length;
const n = matrix[0].length;
const ans: number[] = [];
const vis: boolean[][] = Array.from({ length: m }, () => Array(n).fill(false));
const dirs = [0, 1, 0, -1, 0];
for (let h = m * n, i = 0, j = 0, k = 0; h > 0; --h) {
ans.push(matrix[i][j]);
vis[i][j] = true;
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y]) {
k = (k + 1) % 4;
}
i += dirs[k];
j += dirs[k + 1];
}
return ans;
}func spiralOrder(matrix [][]int) (ans []int) {
m, n := len(matrix), len(matrix[0])
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
dirs := [5]int{0, 1, 0, -1, 0}
i, j, k := 0, 0, 0
for h := m * n; h > 0; h-- {
ans = append(ans, matrix[i][j])
vis[i][j] = true
x, y := i+dirs[k], j+dirs[k+1]
if x < 0 || x >= m || y < 0 || y >= n || vis[x][y] {
k = (k + 1) % 4
}
i, j = i+dirs[k], j+dirs[k+1]
}
return
}impl Solution {
pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
let m = matrix.len();
let n = matrix[0].len();
let mut dirs = vec![0, 1, 0, -1, 0];
let mut vis = vec![vec![false; n]; m];
let mut i = 0;
let mut j = 0;
let mut k = 0;
let mut ans = Vec::new();
for _ in 0..(m * n) {
ans.push(matrix[i][j]);
vis[i][j] = true;
let x = i as i32 + dirs[k] as i32;
let y = j as i32 + dirs[k + 1] as i32;
if x < 0 || x >= m as i32 || y < 0 || y >= n as i32 || vis[x as usize][y as usize] {
k = (k + 1) % 4;
}
i = (i as i32 + dirs[k] as i32) as usize;
j = (j as i32 + dirs[k + 1] as i32) as usize;
}
ans
}
}Approach 4: Simulation (Space Optimization)
Notice that the range of matrix element values is [-100, 100]. Therefore, we can add a large value, such as 300, to the visited elements. This way, we only need to check if the visited element is greater than 100, without needing extra space to record whether it has been visited. If we need to restore the original values of the visited elements, we can traverse the matrix again after the traversal is complete and subtract 300 from all elements.
The time complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).
function spiralOrder(matrix: number[][]): number[] {
const m = matrix.length;
const n = matrix[0].length;
const ans: number[] = [];
const dirs = [0, 1, 0, -1, 0];
for (let h = m * n, i = 0, j = 0, k = 0; h > 0; --h) {
ans.push(matrix[i][j]);
matrix[i][j] += 300;
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] > 100) {
k = (k + 1) % 4;
}
i += dirs[k];
j += dirs[k + 1];
}
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
matrix[i][j] -= 300;
}
}
return ans;
}func spiralOrder(matrix [][]int) (ans []int) {
m, n := len(matrix), len(matrix[0])
dirs := [5]int{0, 1, 0, -1, 0}
i, j, k := 0, 0, 0
for h := m * n; h > 0; h-- {
ans = append(ans, matrix[i][j])
matrix[i][j] += 300
x, y := i+dirs[k], j+dirs[k+1]
if x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] > 100 {
k = (k + 1) % 4
}
i, j = i+dirs[k], j+dirs[k+1]
}
for i = 0; i < m; i++ {
for j = 0; j < n; j++ {
matrix[i][j] -= 300
}
}
return
}impl Solution {
pub fn spiral_order(mut matrix: Vec<Vec<i32>>) -> Vec<i32> {
let m = matrix.len();
let n = matrix[0].len();
let mut dirs = vec![0, 1, 0, -1, 0];
let mut i = 0;
let mut j = 0;
let mut k = 0;
let mut ans = Vec::new();
for _ in 0..(m * n) {
ans.push(matrix[i][j]);
matrix[i][j] += 300;
let x = i as i32 + dirs[k] as i32;
let y = j as i32 + dirs[k + 1] as i32;
if x < 0
|| x >= m as i32
|| y < 0
|| y >= n as i32
|| matrix[x as usize][y as usize] > 100
{
k = (k + 1) % 4;
}
i = (i as i32 + dirs[k] as i32) as usize;
j = (j as i32 + dirs[k + 1] as i32) as usize;
}
for i in 0..m {
for j in 0..n {
matrix[i][j] -= 300;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Boundary Management | Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. Space Complexity: O(1) additional space, excluding the result list. |
| Recursive Divide and Conquer | Time Complexity: O(m * n) since each recursive call processes an entire layer of the matrix. Space Complexity: O(m * n) due to the recursive call stack usage, although tail recursion may optimize this depending on the Python implementation. |
| Simulation | – |
| Simulation (Space Optimization) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Boundary Management | O(m×n) | O(1) | Best general solution. Efficient traversal with constant extra memory. |
| Recursive Divide and Conquer | O(m×n) | O(m+n) recursion stack | Useful for conceptual clarity or recursion practice when processing matrix layers. |
Frequently asked questions
Is Spiral Matrix easy or hard?
Spiral Matrix is considered a medium difficulty problem. The core idea is straightforward, but correctly updating boundaries and avoiding duplicate traversal when rows or columns collapse requires careful implementation.
How to solve Spiral Matrix in O(n)?
For an m×n matrix, the optimal complexity is O(m×n) because every element must be visited to produce the output order. The typical solution uses boundary pointers to simulate spiral movement across rows and columns. This ensures each element is appended once while maintaining constant extra space.
What is the best approach for Spiral Matrix?
The best approach uses iterative boundary management. Maintain four pointers (top, bottom, left, right) and traverse the matrix edges while shrinking the boundaries after each direction. Every element is visited exactly once, giving O(m×n) time and O(1) extra space. This is the solution most interviewers expect.
What data structure is used in Spiral Matrix?
The problem primarily uses a 2D array (matrix). The algorithm relies on index boundaries rather than additional data structures, which keeps space complexity at O(1). The result is stored in a list or array while traversing the matrix in spiral order.
What is the time complexity of Spiral Matrix?
The time complexity is O(m×n) where m is the number of rows and n is the number of columns. Each matrix element is processed exactly once during the spiral traversal. No repeated scans occur, so the runtime grows linearly with the number of elements.
Spiral Matrix Python or Java solution approach?
Both Python and Java implementations follow the same logic: maintain four boundaries and iterate across rows or columns depending on the current direction. After each traversal, update the boundary pointer. The algorithm remains O(m×n) time and O(1) extra space regardless of language.
Is Spiral Matrix asked at Google, Amazon, or Meta?
Spiral Matrix appears frequently in coding interviews at large tech companies including Amazon, Google, and Meta. The problem tests matrix traversal, careful index management, and edge‑case handling when rows or columns shrink during iteration.