Spiral Matrix
💻 Try it yourself first. Write your solution in Java, C++, Python or JavaScript and run it against hidden tests, right here. 🎮 Play SnakeBot: a mini-game built on this problem. Works on your phone too. Pass Submit to unlock every round.On this page
Revision notes
Spiral Matrix (interview style)
Video: “Print the Matrix in a Spiral Manner” on LearnWithKiriti (Kodee, Mr. Tock and SnakeBot). Arrays series, episode 12. LeetCode 54, Medium.
Given an m x n matrix, return all of its elements in spiral order: clockwise, starting at the top left.
Example: [[1,2,3,4],[10,11,12,5],[9,8,7,6]] -> [1,2,3,4,5,6,7,8,9,10,11,12].
| Folder | Approach | Time | Extra space |
|---|---|---|---|
Brute/ |
SnakeBot v1, look ahead and turn: go right, and turn clockwise when the next cell is off the grid or already visited (a visited grid) |
O(m*n) | O(m*n) |
Optimal/ |
SnakeBot v2, four walls (peel the onion): walk the top row, right column, bottom row and left column, moving each wall inward | O(m*n) | O(1) (the answer list is not counted) |
FollowUp-SpiralMatrixII/ |
LeetCode 59: build an n x n matrix filled 1 to n^2 in spiral order. Same four walls, but write instead of read | O(n^2) | O(1) (the answer matrix is not counted) |
Rebuild it
Right, down, left, up. Shrink the wall. Check before you turn back. Keep four walls: top, bottom, left, right. Walk the top row and move top down. Walk the right column and move right in. Before walking back along the bottom row, check top <= bottom. Before walking up the left column, check left <= right.
Why the two checks? After the top row and the right column, the walls may have crossed: only one row or one column was left. Without the checks:
[[1,2,3,4],[10,11,12,5],[9,8,7,6]]gives[1,2,3,4,5,6,7,8,9,10,11,12,11](11 twice: the snake bites itself)[[1,2,3]]gives[1,2,3,2,1][[1],[2],[3]]gives[1,2,3,2]- but the 3 x 3 example is still right, which is why the bug passes the sample and fails on submit.
Play it: the SnakeBot game is in the free Kodee Practice Chrome extension (link in the video description).
Related: Spiral Matrix III (LeetCode 885) and Spiral Matrix IV (LeetCode 2326) use the same walk.
See the pseudocode.md in each folder. Every program was compiled, run and tested (the Python versions were also random-tested against an independent oracle on 3,000 random matrices).
Brute
R1 Brute: SnakeBot v1, look ahead and turn (direction + visited grid)
rows = matrix.length; cols = matrix[0].length
result = []; visited = grid of false
row = 0; col = 0; direction = 0 (0 right, 1 down, 2 left, 3 up)
repeat rows*cols times:
result.add(matrix[row][col]); visited[row][col] = true
nextRow = row + rowStep[direction]; nextCol = col + colStep[direction]
if outside the grid or visited[nextRow][nextCol]:
direction = (direction + 1) % 4
nextRow = row + rowStep[direction]; nextCol = col + colStep[direction]
row = nextRow; col = nextCol
return result
rowStep = [0, 1, 0, -1], colStep = [1, 0, -1, 0]. Derivation (blank mind): be a robot with a finger on the grid; go right until you can’t, then turn clockwise. “Can’t” = off the grid or already visited, so keep a visited grid. Proof: each step prints one new cell, never a visited one; after a turn a free neighbour exists until all cells are printed, so exactly mn steps print each cell once. The outside test comes first so visited is never read out of range. Complexity: O(mn) time, O(m*n) extra (visited) plus the output. Dry run (clock paused) on [[1,2,3],[4,5,6]]: 1, 2, 3, off grid -> down, 6, off grid -> left, 5, 4 -> [1,2,3,6,5,4]. Code dry run on [[1,2,3,4],[10,11,12,5],[9,8,7,6]]: 1,2,3,4 turn down; 5,6 turn left; 7,8,9 turn up; 10 (next is the visited 1) turn right; 11,12 -> 12 steps, 1 to 12, matches.
import java.util.*;
public class SpiralOrderBrute {
static List<Integer> spiralOrder(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
List<Integer> result = new ArrayList<>();
boolean[][] visited = new boolean[rows][cols];
int[] rowStep = {0, 1, 0, -1};
int[] colStep = {1, 0, -1, 0};
int row = 0;
int col = 0;
int direction = 0;
for (int step = 0; step < rows * cols; step++) {
result.add(matrix[row][col]);
visited[row][col] = true;
int nextRow = row + rowStep[direction];
int nextCol = col + colStep[direction];
boolean rowOutside = nextRow < 0 || nextRow >= rows;
boolean colOutside = nextCol < 0 || nextCol >= cols;
if (rowOutside || colOutside || visited[nextRow][nextCol]) {
direction = (direction + 1) % 4;
nextRow = row + rowStep[direction];
nextCol = col + colStep[direction];
}
row = nextRow;
col = nextCol;
}
return result;
}
static String show(Object o) {
if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
return String.valueOf(o);
}
public static void main(String[] args) {
System.out.println(show(spiralOrder(new int[][]{{1, 2, 3}, {8, 9, 4}, {7, 6, 5}})));
System.out.println(show(spiralOrder(new int[][]{{1, 2, 3, 4}, {10, 11, 12, 5}, {9, 8, 7, 6}})));
System.out.println(show(spiralOrder(new int[][]{{1, 2, 3}})));
System.out.println(show(spiralOrder(new int[][]{{1}, {2}, {3}})));
}
}#include <bits/stdc++.h>
using namespace std;
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
vector<int> result;
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
int rowStep[4] = {0, 1, 0, -1};
int colStep[4] = {1, 0, -1, 0};
int row = 0;
int col = 0;
int direction = 0;
for (int step = 0; step < rows * cols; step++) {
result.push_back(matrix[row][col]);
visited[row][col] = true;
int nextRow = row + rowStep[direction];
int nextCol = col + colStep[direction];
bool rowOutside = nextRow < 0 || nextRow >= rows;
bool colOutside = nextCol < 0 || nextCol >= cols;
if (rowOutside || colOutside || visited[nextRow][nextCol]) {
direction = (direction + 1) % 4;
nextRow = row + rowStep[direction];
nextCol = col + colStep[direction];
}
row = nextRow;
col = nextCol;
}
return result;
}
string show(int value) { return to_string(value); }
string show(long long value) { return to_string(value); }
string show(bool value) { return value ? "true" : "false"; }
string show(const string& value) { return "\"" + value + "\""; }
template <typename T> string show(const vector<T>& values) {
string text = "[";
for (size_t index = 0; index < values.size(); index++) {
text += (index ? ", " : "") + show(values[index]);
}
return text + "]";
}
int main() {
{ auto arg0 = vector<vector<int>>{{1, 2, 3}, {8, 9, 4}, {7, 6, 5}}; cout << show(spiralOrder(arg0)) << endl; }
{ auto arg0 = vector<vector<int>>{{1, 2, 3, 4}, {10, 11, 12, 5}, {9, 8, 7, 6}}; cout << show(spiralOrder(arg0)) << endl; }
{ auto arg0 = vector<vector<int>>{{1, 2, 3}}; cout << show(spiralOrder(arg0)) << endl; }
{ auto arg0 = vector<vector<int>>{{1}, {2}, {3}}; cout << show(spiralOrder(arg0)) << endl; }
return 0;
}import json
def spiral_order(matrix):
rows = len(matrix)
cols = len(matrix[0])
result = []
visited = [[False] * cols for row_index in range(rows)]
row_step = [0, 1, 0, -1]
col_step = [1, 0, -1, 0]
row = 0
col = 0
direction = 0
for step in range(rows * cols):
result.append(matrix[row][col])
visited[row][col] = True
next_row = row + row_step[direction]
next_col = col + col_step[direction]
row_outside = next_row < 0 or next_row >= rows
col_outside = next_col < 0 or next_col >= cols
if row_outside or col_outside or visited[next_row][next_col]:
direction = (direction + 1) % 4
next_row = row + row_step[direction]
next_col = col + col_step[direction]
row = next_row
col = next_col
return result
if __name__ == "__main__":
print(json.dumps(spiral_order([[1, 2, 3], [8, 9, 4], [7, 6, 5]])).replace(',', ', '))
print(json.dumps(spiral_order([[1, 2, 3, 4], [10, 11, 12, 5], [9, 8, 7, 6]])).replace(',', ', '))
print(json.dumps(spiral_order([[1, 2, 3]])).replace(',', ', '))
print(json.dumps(spiral_order([[1], [2], [3]])).replace(',', ', '))function spiralOrder(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
const result = [];
const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
const rowStep = [0, 1, 0, -1];
const colStep = [1, 0, -1, 0];
let row = 0;
let col = 0;
let direction = 0;
for (let step = 0; step < rows * cols; step++) {
result.push(matrix[row][col]);
visited[row][col] = true;
let nextRow = row + rowStep[direction];
let nextCol = col + colStep[direction];
const rowOutside = nextRow < 0 || nextRow >= rows;
const colOutside = nextCol < 0 || nextCol >= cols;
if (rowOutside || colOutside || visited[nextRow][nextCol]) {
direction = (direction + 1) % 4;
nextRow = row + rowStep[direction];
nextCol = col + colStep[direction];
}
row = nextRow;
col = nextCol;
}
return result;
}
console.log(JSON.stringify(spiralOrder([[1, 2, 3], [8, 9, 4], [7, 6, 5]])).replace(/,/g, ', '));
console.log(JSON.stringify(spiralOrder([[1, 2, 3, 4], [10, 11, 12, 5], [9, 8, 7, 6]])).replace(/,/g, ', '));
console.log(JSON.stringify(spiralOrder([[1, 2, 3]])).replace(/,/g, ', '));
console.log(JSON.stringify(spiralOrder([[1], [2], [3]])).replace(/,/g, ', '));Optimal
R2 Optimal: SnakeBot v2, four walls (peel the onion)
result = []; top = 0; bottom = rows-1; left = 0; right = cols-1
while top <= bottom and left <= right:
for col from left to right: result.add(matrix[top][col]); top += 1
for row from top to bottom: result.add(matrix[row][right]); right -= 1
if top <= bottom:
for col from right down to left: result.add(matrix[bottom][col]); bottom -= 1
if left <= right:
for row from bottom down to top: result.add(matrix[row][left]); left += 1
return result
Derivation: in R1 the visited cells always form a frame around the unvisited block, so remember only the frame’s four edges (four numbers) instead of the whole grid. Proof of the two guards: the while condition guarantees a row and a column exist, so the top row and right column are safe. After they are walked and their walls move in, the block may have collapsed to a single row (top > bottom) or a single column (left > right); then the bottom row or left column would re-read cells already printed. Without the guards: 3x3 stays correct (hides the bug); 3x4 [[1,2,3,4],[10,11,12,5],[9,8,7,6]] -> [1,…,12,11] (eats 11 twice); [[1,2,3]] -> [1,2,3,2,1]; [[1],[2],[3]] -> [1,2,3,2]. Honest alternative: stop when result has mn numbers; also works. Other styles (one sentence): recursion on the inner layer (stack space), overwrite visited cells (destroys input). Complexity: O(mn) time, O(1) extra besides the output. Dry run (clock paused): [[1],[2],[3]] -> top row 1; right col 2,3 (right=-1); bottom loop empty; left guard false -> [1,2,3]. [[1,2,3]] -> top row 1,2,3; right col none; bottom guard false; left loop empty -> [1,2,3]. Code dry run on [[1,2,3,4],[10,11,12,5],[9,8,7,6]]: pass 1 top 1,2,3,4; right 5,6; bottom 7,8,9; left 10; pass 2 top 11,12; right none; bottom guard false (top 2 > bottom 1); left none; ends -> matches.
import java.util.*;
public class SpiralOrder {
static List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
int top = 0;
int bottom = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (int col = left; col <= right; col++) {
result.add(matrix[top][col]);
}
top++;
for (int row = top; row <= bottom; row++) {
result.add(matrix[row][right]);
}
right--;
if (top <= bottom) {
for (int col = right; col >= left; col--) {
result.add(matrix[bottom][col]);
}
bottom--;
}
if (left <= right) {
for (int row = bottom; row >= top; row--) {
result.add(matrix[row][left]);
}
left++;
}
}
return result;
}
static String show(Object o) {
if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
return String.valueOf(o);
}
public static void main(String[] args) {
System.out.println(show(spiralOrder(new int[][]{{1, 2, 3}, {8, 9, 4}, {7, 6, 5}})));
System.out.println(show(spiralOrder(new int[][]{{1, 2, 3, 4}, {10, 11, 12, 5}, {9, 8, 7, 6}})));
System.out.println(show(spiralOrder(new int[][]{{1, 2, 3}})));
System.out.println(show(spiralOrder(new int[][]{{1}, {2}, {3}})));
}
}#include <bits/stdc++.h>
using namespace std;
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> result;
int top = 0;
int bottom = matrix.size() - 1;
int left = 0;
int right = matrix[0].size() - 1;
while (top <= bottom && left <= right) {
for (int col = left; col <= right; col++) {
result.push_back(matrix[top][col]);
}
top++;
for (int row = top; row <= bottom; row++) {
result.push_back(matrix[row][right]);
}
right--;
if (top <= bottom) {
for (int col = right; col >= left; col--) {
result.push_back(matrix[bottom][col]);
}
bottom--;
}
if (left <= right) {
for (int row = bottom; row >= top; row--) {
result.push_back(matrix[row][left]);
}
left++;
}
}
return result;
}
string show(int value) { return to_string(value); }
string show(long long value) { return to_string(value); }
string show(bool value) { return value ? "true" : "false"; }
string show(const string& value) { return "\"" + value + "\""; }
template <typename T> string show(const vector<T>& values) {
string text = "[";
for (size_t index = 0; index < values.size(); index++) {
text += (index ? ", " : "") + show(values[index]);
}
return text + "]";
}
int main() {
{ auto arg0 = vector<vector<int>>{{1, 2, 3}, {8, 9, 4}, {7, 6, 5}}; cout << show(spiralOrder(arg0)) << endl; }
{ auto arg0 = vector<vector<int>>{{1, 2, 3, 4}, {10, 11, 12, 5}, {9, 8, 7, 6}}; cout << show(spiralOrder(arg0)) << endl; }
{ auto arg0 = vector<vector<int>>{{1, 2, 3}}; cout << show(spiralOrder(arg0)) << endl; }
{ auto arg0 = vector<vector<int>>{{1}, {2}, {3}}; cout << show(spiralOrder(arg0)) << endl; }
return 0;
}import json
def spiral_order(matrix):
result = []
top = 0
bottom = len(matrix) - 1
left = 0
right = len(matrix[0]) - 1
while top <= bottom and left <= right:
for col in range(left, right + 1):
result.append(matrix[top][col])
top += 1
for row in range(top, bottom + 1):
result.append(matrix[row][right])
right -= 1
if top <= bottom:
for col in range(right, left - 1, -1):
result.append(matrix[bottom][col])
bottom -= 1
if left <= right:
for row in range(bottom, top - 1, -1):
result.append(matrix[row][left])
left += 1
return result
if __name__ == "__main__":
print(json.dumps(spiral_order([[1, 2, 3], [8, 9, 4], [7, 6, 5]])).replace(',', ', '))
print(json.dumps(spiral_order([[1, 2, 3, 4], [10, 11, 12, 5], [9, 8, 7, 6]])).replace(',', ', '))
print(json.dumps(spiral_order([[1, 2, 3]])).replace(',', ', '))
print(json.dumps(spiral_order([[1], [2], [3]])).replace(',', ', '))function spiralOrder(matrix) {
const result = [];
let top = 0;
let bottom = matrix.length - 1;
let left = 0;
let right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (let col = left; col <= right; col++) {
result.push(matrix[top][col]);
}
top++;
for (let row = top; row <= bottom; row++) {
result.push(matrix[row][right]);
}
right--;
if (top <= bottom) {
for (let col = right; col >= left; col--) {
result.push(matrix[bottom][col]);
}
bottom--;
}
if (left <= right) {
for (let row = bottom; row >= top; row--) {
result.push(matrix[row][left]);
}
left++;
}
}
return result;
}
console.log(JSON.stringify(spiralOrder([[1, 2, 3], [8, 9, 4], [7, 6, 5]])).replace(/,/g, ', '));
console.log(JSON.stringify(spiralOrder([[1, 2, 3, 4], [10, 11, 12, 5], [9, 8, 7, 6]])).replace(/,/g, ', '));
console.log(JSON.stringify(spiralOrder([[1, 2, 3]])).replace(/,/g, ', '));
console.log(JSON.stringify(spiralOrder([[1], [2], [3]])).replace(/,/g, ', '));Follow-up: Spiral Matrix II
R3 Follow-up: Spiral Matrix II (LeetCode 59, Medium): build n x n filled 1 to n^2
matrix = size x size of zeros; top = 0; bottom = size-1; left = 0; right = size-1; value = 1
while top <= bottom and left <= right:
top row left->right, right col top->bottom, (if top <= bottom) bottom row right->left,
(if left <= right) left col bottom->top: each cell: matrix[..][..] = value; value += 1; then move that wall in
return matrix
Derivation: same walk, flip read to write. For a square the guards never change the answer (the loops they skip would be empty; verified n = 1 to 11); keep them so it is safe for any m x n. Complexity: O(n^2) time, O(1) extra besides the output. Dry run n=3: top 1,2,3; right 4,5; bottom 6,7; left 8; inner 9 -> [[1,2,3],[8,9,4],[7,6,5]]. Cards: LeetCode 885 (walk outward from a start cell), LeetCode 2326 (fill from a linked list), links in the description.
import java.util.*;
public class GenerateMatrix {
static int[][] generateMatrix(int size) {
int[][] matrix = new int[size][size];
int top = 0;
int bottom = size - 1;
int left = 0;
int right = size - 1;
int value = 1;
while (top <= bottom && left <= right) {
for (int col = left; col <= right; col++) {
matrix[top][col] = value;
value++;
}
top++;
for (int row = top; row <= bottom; row++) {
matrix[row][right] = value;
value++;
}
right--;
if (top <= bottom) {
for (int col = right; col >= left; col--) {
matrix[bottom][col] = value;
value++;
}
bottom--;
}
if (left <= right) {
for (int row = bottom; row >= top; row--) {
matrix[row][left] = value;
value++;
}
left++;
}
}
return matrix;
}
static String show(Object o) {
if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
return String.valueOf(o);
}
public static void main(String[] args) {
System.out.println(show(generateMatrix(1)));
System.out.println(show(generateMatrix(3)));
System.out.println(show(generateMatrix(4)));
}
}#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> generateMatrix(int size) {
vector<vector<int>> matrix(size, vector<int>(size, 0));
int top = 0;
int bottom = size - 1;
int left = 0;
int right = size - 1;
int value = 1;
while (top <= bottom && left <= right) {
for (int col = left; col <= right; col++) {
matrix[top][col] = value;
value++;
}
top++;
for (int row = top; row <= bottom; row++) {
matrix[row][right] = value;
value++;
}
right--;
if (top <= bottom) {
for (int col = right; col >= left; col--) {
matrix[bottom][col] = value;
value++;
}
bottom--;
}
if (left <= right) {
for (int row = bottom; row >= top; row--) {
matrix[row][left] = value;
value++;
}
left++;
}
}
return matrix;
}
string show(int value) { return to_string(value); }
string show(long long value) { return to_string(value); }
string show(bool value) { return value ? "true" : "false"; }
string show(const string& value) { return "\"" + value + "\""; }
template <typename T> string show(const vector<T>& values) {
string text = "[";
for (size_t index = 0; index < values.size(); index++) {
text += (index ? ", " : "") + show(values[index]);
}
return text + "]";
}
int main() {
{ auto arg0 = 1; cout << show(generateMatrix(arg0)) << endl; }
{ auto arg0 = 3; cout << show(generateMatrix(arg0)) << endl; }
{ auto arg0 = 4; cout << show(generateMatrix(arg0)) << endl; }
return 0;
}import json
def generate_matrix(size):
matrix = [[0] * size for row_index in range(size)]
top = 0
bottom = size - 1
left = 0
right = size - 1
value = 1
while top <= bottom and left <= right:
for col in range(left, right + 1):
matrix[top][col] = value
value += 1
top += 1
for row in range(top, bottom + 1):
matrix[row][right] = value
value += 1
right -= 1
if top <= bottom:
for col in range(right, left - 1, -1):
matrix[bottom][col] = value
value += 1
bottom -= 1
if left <= right:
for row in range(bottom, top - 1, -1):
matrix[row][left] = value
value += 1
left += 1
return matrix
if __name__ == "__main__":
print(json.dumps(generate_matrix(1)).replace(',', ', '))
print(json.dumps(generate_matrix(3)).replace(',', ', '))
print(json.dumps(generate_matrix(4)).replace(',', ', '))function generateMatrix(size) {
const matrix = Array.from({ length: size }, () => new Array(size).fill(0));
let top = 0;
let bottom = size - 1;
let left = 0;
let right = size - 1;
let value = 1;
while (top <= bottom && left <= right) {
for (let col = left; col <= right; col++) {
matrix[top][col] = value;
value++;
}
top++;
for (let row = top; row <= bottom; row++) {
matrix[row][right] = value;
value++;
}
right--;
if (top <= bottom) {
for (let col = right; col >= left; col--) {
matrix[bottom][col] = value;
value++;
}
bottom--;
}
if (left <= right) {
for (let row = bottom; row >= top; row--) {
matrix[row][left] = value;
value++;
}
left++;
}
}
return matrix;
}
console.log(JSON.stringify(generateMatrix(1)).replace(/,/g, ', '));
console.log(JSON.stringify(generateMatrix(3)).replace(/,/g, ', '));
console.log(JSON.stringify(generateMatrix(4)).replace(/,/g, ', '));