Spiral Matrix
You're twenty minutes into a Microsoft interview when the interviewer slides a grid of numbers across the table. "Read these values back to me in a spiral," they say, tracing a clockwise path with their finger from the top-left corner inward. This is the Spiral Matrix problem, a staple at companies like Microsoft and Amazon. It tests whether you can move through a 2D grid while keeping exact track of which rows and columns are already done.
TL;DR
Keep four bounds: top, bottom, left and right. Read the top row, then move top down. Read the right column, then move right in. Read the bottom row backwards, then move bottom up. Read the left column upwards, then move left in. After each edge, stop as soon as a bound passes the one opposite it. This runs in O(m * n) time and O(1) extra space.
Why This Problem Matters
Spiral traversal appears regularly in technical interviews because it combines matrix indexing, simulation and boundary checks in one short problem. Getting the logic 90% right still produces wrong output, so it rewards precision. The shrinking-bounds idea also comes back in other layer-by-layer matrix problems, such as rotating a square image.
Understanding the Problem
You are given matrix, a grid of integers with m rows and n columns. Return all of its elements in spiral order.
Spiral order starts at the top-left element and goes clockwise around the outside of the grid: right along the top row, down the right column, left along the bottom row and up the left column. It then does the same on the part that is left inside, until every element is read once.
Constraints
- 1 <=
m,n<= 10 - -100 <=
matrix[i][j]<= 100
Here's a 3x3 matrix to visualize the grid:
Loading visualization...
The spiral order for this grid is [1, 2, 3, 6, 9, 8, 7, 4, 5]. Starting from the top-left, we move right along the first row, down the last column, left along the bottom row, up the first column, and finally reach the center.
Loading visualization...
A taller example: dumpSpiral([[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15]]) returns [1, 2, 3, 6, 9, 12, 15, 14, 13, 10, 7, 4, 5, 8, 11]. The outer ring is read clockwise, starting at 1 and ending at 4. Then only the middle column is left, and 5, 8 and 11 are read once, from top to bottom.
Prefer a different language? Jump to solutions in other languages.
Edge Cases to Consider
- Single row (
[[1,3]]): read left to right, then stop - Single column (
[[1],[3]]): read the one top element, then down the column, then stop - 2x2 matrix: one complete ring with no inner cells
- Rectangular matrices: the last ring is often a single row or column, and it must not be read twice
Solution Approach
Spiral order reads the outer ring clockwise, then the ring inside it, and so on. The question is how to record which rows and columns are already read. Four integers are enough:
top: the first row that is not read yetbottom: the last row that is not read yetleft: the first column that is not read yetright: the last column that is not read yet
Together they mark out the rectangle that is still unread.
Reading One Ring
Each pass of the loop reads the four edges of the unread rectangle, and each edge removes one row or one column from it:
- Read row
topfromlefttoright. That row is done, sotopmoves down by one. - Read column
rightfromtoptobottom. That column is done, sorightmoves left by one. - Read row
bottomfromrighttoleft. That row is done, sobottommoves up by one. - Read column
leftfrombottomtotop. That column is done, soleftmoves right by one.
Stopping at the Right Moment
After each edge, the unread rectangle may be empty. If top > bottom, no rows are left. If left > right, no columns are left. The loop must stop right there, even in the middle of a ring.
This check is what makes single rows and single columns work. Take [[1,2,3]]. The top row gives 1, 2, 3, and top becomes 1 while bottom is 0. Without a check, the loop would go on and read the bottom row, which is the same row, backwards. The output would then contain 2 and 1 a second time.
Tracing a 2x2 Matrix
Let's trace [[1,2],[3,4]]. The bounds start at top = 0, bottom = 1, left = 0, right = 1.
Loading visualization...
Step 1: Read row 0 from column 0 to 1: 1, 2. Set top = 1. Rows 1 to 1 are left, so continue.
Step 2: Read column 1 from row 1 to 1: 4. Set right = 0. Columns 0 to 0 are left, so continue.
Step 3: Read row 1 from column 0 to 0: 3. Set bottom = 0. Now top > bottom, so stop.
Result: [1, 2, 4, 3]
Non-Square Matrices
Rows and columns shrink independently, so rectangles need no special handling. Here dumpSpiral([[1,2,3],[4,5,6]]) returns [1, 2, 3, 6, 5, 4]:
Loading visualization...
The top row gives 1, 2, 3. The right column now has only row 1 left, which gives 6. The bottom row is read from column 1 back to column 0, which gives 5, 4. Then bottom moves above top, and the loop stops.
Implementation
Here's the Java solution:
import java.util.ArrayList;
import java.util.List;
public class Solution {
/**
* Returns the integers in the matrix in clockwise
* spiral order.
*
* @param matrix Input matrix.
* @return List of integers in clockwise spiral order.
*/
public List<Integer> dumpSpiral(int[][] matrix) {
List<Integer> result = new ArrayList<>();
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while (true) {
for (int col = left; col <= right; col++) {
result.add(matrix[top][col]);
}
top++;
if (top > bottom) break;
for (int row = top; row <= bottom; row++) {
result.add(matrix[row][right]);
}
right--;
if (left > right) break;
for (int col = right; col >= left; col--) {
result.add(matrix[bottom][col]);
}
bottom--;
if (top > bottom) break;
for (int row = bottom; row >= top; row--) {
result.add(matrix[row][left]);
}
left++;
if (left > right) break;
}
return result;
}
}
The while (true) loop reads one ring per pass. Each for loop reads one edge, and the line after it shrinks the matching bound. The break after each edge ends the traversal as soon as no rows or no columns are left, which also means the loop never needs a separate count of elements.
Complexity Analysis
Time Complexity: O(m * n)
Each element is added to result exactly once, because every edge read removes its row or column from the unread rectangle. The bound updates and checks are O(1) per edge. For an m x n matrix, that is O(m * n) work in total.
Space Complexity: O(1)
The algorithm uses four integer bounds and a loop index, whatever the size of the matrix. The result list has m * n elements, but it is the required output and is not counted as extra space. No visited grid is needed, because the bounds already record which rows and columns are done.
Common Pitfalls
-
Checking the bounds only once per ring: if the loop checks only at the top of each pass, a last single row or column is read twice. Check after every edge.
-
Comparing the wrong pair of bounds: after reading a row, compare
topwithbottom. After reading a column, compareleftwithright. Mixing them up stops too early or reads too far. -
Off-by-one loop ranges: every edge range is inclusive at both ends, from
lefttorightor fromtoptobottom. An exclusive end skips the corner element. -
Assuming square matrices: using the row count for both dimensions breaks rectangular inputs. Take
bottomfrom the row count andrightfrom the column count.
Interview Tips
When solving this in an interview:
-
Start with a small example: draw a 3x3 grid and trace the spiral by hand. This helps you and the interviewer agree on the expected output before you write code.
-
Name the bounds out loud: say what
top,bottom,leftandrightmean before you code. It makes each loop range easy to explain. -
Test a single row early: run
[[1,3]]through your code by hand. It is the quickest way to show that the check after each edge is needed. -
Mention the alternative: a visited grid with direction turning also works, but it needs O(m * n) extra space. The bounds approach avoids that.
-
Watch for follow-ups: a common follow-up is to fill an n x n matrix with 1 to n squared in spiral order. The same four bounds work, with writes in place of reads.
Key Takeaways
- Four bounds,
top,bottom,leftandright, describe the rectangle that is still unread. - Each edge read shrinks exactly one bound: the top row moves
topdown, the right column movesrightin, and so on. - Checking
top > bottomorleft > rightafter every edge prevents a last single row or column from being read twice. - Every element is read once, so the time is O(m * n), and the bounds take O(1) extra space.
- The shrinking-bounds idea also applies to other layer-by-layer matrix problems.
Related Problems and Practice
Once you're comfortable with spiral traversal, try these related problems:
- Image matrix 90-degree twist (matrix rotation also works layer by layer)
- Zero out rows and columns (another matrix traversal pattern)
- Number of islands (grid traversal with neighbor checks)
Solutions in Other Languages
Every version below uses the same four bounds and the same check after each edge.
Python
from typing import List
class Solution:
def dump_spiral(self, matrix: List[List[int]]) -> List[int]:
"""
Returns the integers in the matrix in clockwise
spiral order.
:param matrix: Input matrix.
:return: List of integers in clockwise spiral order.
"""
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while True:
for col in range(left, right + 1):
result.append(matrix[top][col])
top += 1
if top > bottom:
break
for row in range(top, bottom + 1):
result.append(matrix[row][right])
right -= 1
if left > right:
break
for col in range(right, left - 1, -1):
result.append(matrix[bottom][col])
bottom -= 1
if top > bottom:
break
for row in range(bottom, top - 1, -1):
result.append(matrix[row][left])
left += 1
if left > right:
break
return result
JavaScript
class Solution {
/**
* Returns the integers in the matrix in clockwise
* spiral order.
*
* @param {Array<Array<number>>} matrix Input matrix.
* @return {Array<number>} List of integers in clockwise spiral order.
*/
dumpSpiral(matrix) {
const result = [];
let top = 0, bottom = matrix.length - 1;
let left = 0, right = matrix[0].length - 1;
while (true) {
for (let col = left; col <= right; col++) {
result.push(matrix[top][col]);
}
top++;
if (top > bottom) break;
for (let row = top; row <= bottom; row++) {
result.push(matrix[row][right]);
}
right--;
if (left > right) break;
for (let col = right; col >= left; col--) {
result.push(matrix[bottom][col]);
}
bottom--;
if (top > bottom) break;
for (let row = bottom; row >= top; row--) {
result.push(matrix[row][left]);
}
left++;
if (left > right) break;
}
return result;
}
}
module.exports = Solution;
TypeScript
class Solution {
/**
* Returns the integers in the matrix in clockwise
* spiral order.
*
* @param matrix - Input matrix.
* @returns List of integers in clockwise spiral order.
*/
dumpSpiral(matrix: number[][]): number[] {
const result: number[] = [];
let top = 0, bottom = matrix.length - 1;
let left = 0, right = matrix[0].length - 1;
while (true) {
for (let col = left; col <= right; col++) {
result.push(matrix[top][col]);
}
top++;
if (top > bottom) break;
for (let row = top; row <= bottom; row++) {
result.push(matrix[row][right]);
}
right--;
if (left > right) break;
for (let col = right; col >= left; col--) {
result.push(matrix[bottom][col]);
}
bottom--;
if (top > bottom) break;
for (let row = bottom; row >= top; row--) {
result.push(matrix[row][left]);
}
left++;
if (left > right) break;
}
return result;
}
}
export { Solution };
C++
#include <vector>
#include <iostream>
class Solution {
public:
/**
* DumpSpiral returns the integers in the matrix in clockwise spiral order
* @param matrix Input matrix.
* @return Vector of integers in clockwise spiral order.
*/
std::vector<int> dumpSpiral(std::vector<std::vector<int>> &matrix) {
std::vector<int> result;
int top = 0, bottom = matrix.size() - 1;
int left = 0, right = matrix[0].size() - 1;
while (true) {
for (int col = left; col <= right; col++) {
result.push_back(matrix[top][col]);
}
top++;
if (top > bottom) break;
for (int row = top; row <= bottom; row++) {
result.push_back(matrix[row][right]);
}
right--;
if (left > right) break;
for (int col = right; col >= left; col--) {
result.push_back(matrix[bottom][col]);
}
bottom--;
if (top > bottom) break;
for (int row = bottom; row >= top; row--) {
result.push_back(matrix[row][left]);
}
left++;
if (left > right) break;
}
return result;
}
};
Go
package solution
// You can import standard packages below, like "fmt" and "strings":
// DumpSpiral returns the integers in the matrix in clockwise spiral order
func (s *Solution) DumpSpiral(matrix [][]int) []int {
result := make([]int, 0)
top, bottom := 0, len(matrix)-1
left, right := 0, len(matrix[0])-1
for {
for col := left; col <= right; col++ {
result = append(result, matrix[top][col])
}
top++
if top > bottom {
break
}
for row := top; row <= bottom; row++ {
result = append(result, matrix[row][right])
}
right--
if left > right {
break
}
for col := right; col >= left; col-- {
result = append(result, matrix[bottom][col])
}
bottom--
if top > bottom {
break
}
for row := bottom; row >= top; row-- {
result = append(result, matrix[row][left])
}
left++
if left > right {
break
}
}
return result
}
// Solution is required to run your method. Do not modify.
type Solution struct {
}
Go has no while loop, so the solution uses a bare for and leaves it with break when two bounds cross.
Scala
Scala has no break, so this version returns result.toList directly from the loop when the bounds cross.
import scala.collection.mutable
class Solution {
/**
* Returns the integers in the matrix in clockwise
* spiral order.
*
* @param matrix Input matrix.
* @return List of integers in clockwise spiral order.
*/
def dumpSpiral(matrix: Array[Array[Int]]): List[Int] = {
val result = mutable.ArrayBuffer[Int]()
var top = 0
var bottom = matrix.length - 1
var left = 0
var right = matrix(0).length - 1
while (true) {
for (col <- left to right) {
result.append(matrix(top)(col))
}
top += 1
if (top > bottom) return result.toList
for (row <- top to bottom) {
result.append(matrix(row)(right))
}
right -= 1
if (left > right) return result.toList
for (col <- right to left by -1) {
result.append(matrix(bottom)(col))
}
bottom -= 1
if (top > bottom) return result.toList
for (row <- bottom to top by -1) {
result.append(matrix(row)(left))
}
left += 1
if (left > right) return result.toList
}
result.toList
}
}
Kotlin
class Solution {
/**
* Returns the integers in the matrix in clockwise
* spiral order.
*
* @param matrix Input matrix.
* @return List of integers in clockwise spiral order.
*/
fun dumpSpiral(matrix: Array<IntArray>): List<Int> {
val result = mutableListOf<Int>()
var top = 0
var bottom = matrix.size - 1
var left = 0
var right = matrix[0].size - 1
while (true) {
for (col in left..right) {
result.add(matrix[top][col])
}
top++
if (top > bottom) break
for (row in top..bottom) {
result.add(matrix[row][right])
}
right--
if (left > right) break
for (col in right downTo left) {
result.add(matrix[bottom][col])
}
bottom--
if (top > bottom) break
for (row in bottom downTo top) {
result.add(matrix[row][left])
}
left++
if (left > right) break
}
return result
}
}
Swift
import Foundation
class Solution {
/**
* Returns the integers in the matrix in clockwise
* spiral order.
*
* - Parameter matrix: Input matrix.
* - Returns: List of integers in clockwise spiral order.
*/
func dumpSpiral(_ matrix: [[Int]]) -> [Int] {
var result: [Int] = []
var top = 0, bottom = matrix.count - 1
var left = 0, right = matrix[0].count - 1
while true {
for col in left...right {
result.append(matrix[top][col])
}
top += 1
if top > bottom { break }
for row in top...bottom {
result.append(matrix[row][right])
}
right -= 1
if left > right { break }
for col in stride(from: right, through: left, by: -1) {
result.append(matrix[bottom][col])
}
bottom -= 1
if top > bottom { break }
for row in stride(from: bottom, through: top, by: -1) {
result.append(matrix[row][left])
}
left += 1
if left > right { break }
}
return result
}
}
Dart
class Solution {
/// Returns the integers in the matrix in clockwise
/// spiral order.
///
/// [matrix] Input matrix.
/// Returns list of integers in clockwise spiral order.
List<int> dumpSpiral(List<List<int>> matrix) {
List<int> result = [];
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while (true) {
for (int col = left; col <= right; col++) {
result.add(matrix[top][col]);
}
top++;
if (top > bottom) break;
for (int row = top; row <= bottom; row++) {
result.add(matrix[row][right]);
}
right--;
if (left > right) break;
for (int col = right; col >= left; col--) {
result.add(matrix[bottom][col]);
}
bottom--;
if (top > bottom) break;
for (int row = bottom; row >= top; row--) {
result.add(matrix[row][left]);
}
left++;
if (left > right) break;
}
return result;
}
}
C#
using System.Collections.Generic;
public class Solution {
/// <summary>
/// Returns the integers in the matrix in clockwise
/// spiral order.
/// </summary>
/// <param name="matrix">Input matrix.</param>
/// <returns>List of integers in clockwise spiral order.</returns>
public List<int> DumpSpiral(int[][] matrix) {
var result = new List<int>();
int top = 0, bottom = matrix.Length - 1;
int left = 0, right = matrix[0].Length - 1;
while (true) {
for (int col = left; col <= right; col++) {
result.Add(matrix[top][col]);
}
top++;
if (top > bottom) break;
for (int row = top; row <= bottom; row++) {
result.Add(matrix[row][right]);
}
right--;
if (left > right) break;
for (int col = right; col >= left; col--) {
result.Add(matrix[bottom][col]);
}
bottom--;
if (top > bottom) break;
for (int row = bottom; row >= top; row--) {
result.Add(matrix[row][left]);
}
left++;
if (left > right) break;
}
return result;
}
}
PHP
<?php
class Solution {
/**
* Returns the integers in the matrix in clockwise
* spiral order.
*
* @param array $matrix Input matrix.
* @return array List of integers in clockwise spiral order.
*/
public function dumpSpiral(array $matrix): array {
$result = [];
$top = 0;
$bottom = count($matrix) - 1;
$left = 0;
$right = count($matrix[0]) - 1;
while (true) {
for ($col = $left; $col <= $right; $col++) {
$result[] = $matrix[$top][$col];
}
$top++;
if ($top > $bottom) break;
for ($row = $top; $row <= $bottom; $row++) {
$result[] = $matrix[$row][$right];
}
$right--;
if ($left > $right) break;
for ($col = $right; $col >= $left; $col--) {
$result[] = $matrix[$bottom][$col];
}
$bottom--;
if ($top > $bottom) break;
for ($row = $bottom; $row >= $top; $row--) {
$result[] = $matrix[$row][$left];
}
$left++;
if ($left > $right) break;
}
return $result;
}
}
Ruby
class Solution
# Returns the integers in the matrix in clockwise
# spiral order.
#
# @param matrix [Array<Array<Integer>>] Input matrix
# @return [Array<Integer>] List of integers in clockwise spiral order
def dump_spiral(matrix)
result = []
top, bottom = 0, matrix.length - 1
left, right = 0, matrix[0].length - 1
loop do
(left..right).each do |col|
result << matrix[top][col]
end
top += 1
break if top > bottom
(top..bottom).each do |row|
result << matrix[row][right]
end
right -= 1
break if left > right
right.downto(left) do |col|
result << matrix[bottom][col]
end
bottom -= 1
break if top > bottom
bottom.downto(top) do |row|
result << matrix[row][left]
end
left += 1
break if left > right
end
result
end
end
Rust
The bounds are i32 so that right and bottom can drop below zero without an underflow. They are cast to usize only for indexing.
pub struct Solution;
impl Solution {
/// Returns the integers in the matrix in clockwise
/// spiral order.
///
/// # Arguments
/// * `matrix` - Input matrix.
///
/// # Returns
/// A Vec<i32> containing integers in clockwise spiral order.
pub fn dump_spiral(&self, matrix: Vec<Vec<i32>>) -> Vec<i32> {
let mut result = Vec::new();
let (mut top, mut bottom) = (0i32, matrix.len() as i32 - 1);
let (mut left, mut right) = (0i32, matrix[0].len() as i32 - 1);
loop {
for col in left..=right {
result.push(matrix[top as usize][col as usize]);
}
top += 1;
if top > bottom {
break;
}
for row in top..=bottom {
result.push(matrix[row as usize][right as usize]);
}
right -= 1;
if left > right {
break;
}
for col in (left..=right).rev() {
result.push(matrix[bottom as usize][col as usize]);
}
bottom -= 1;
if top > bottom {
break;
}
for row in (top..=bottom).rev() {
result.push(matrix[row as usize][left as usize]);
}
left += 1;
if left > right {
break;
}
}
result
}
}
Practice on Firecode
Spiral Matrix is the kind of problem that clicks once you've traced it a few times. The shrinking-bounds pattern shows up in other matrix problems, so time spent here pays off across your interview prep. This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. Build the muscle memory now, and you'll go into your next interview with confidence.