Log inSign up
mediumLeetCodeNot Started

Spiral Matrix

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an m x n matrix, return all elements of the matrix in spiral order, starting from the top-left cell (0, 0) and moving in a clockwise direction.

Example 1 · 3x3 Square Matrix:

Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
Explanation: Start at (0, 0). Move right to collect [1, 2, 3], move down to collect [6, 9], move left to collect [8, 7], move up to collect [4], and finally move into the center to collect [5].

Example 2 · 3x4 Rectangular Matrix (More columns than rows):

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]
Explanation: Outer perimeter yields [1, 2, 3, 4, 8, 12, 11, 10, 9, 5]. Remaining inner elements are [6, 7].

Example 3 · Single Row Matrix (1x4):

Input: matrix = [[1, 2, 3, 4]]
Output: [1, 2, 3, 4]
Explanation: Traverses right across row 0 and immediately terminates because the top boundary exceeds the bottom boundary.

Example 4 · Single Column Matrix (4x1):

Input: matrix = [[1], [2], [3], [4]]
Output: [1, 2, 3, 4]
Explanation: Traverses down column 0 and terminates cleanly.

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D array coordinate indexing (matrix[row][col])
  • Understanding loop conditions and boundary manipulation
  • Handling asymmetric rectangular dimensions (m != n)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 4-boundary bounding box technique for 2D matrix traversal.
  • Understand why single-row and single-column edge cases cause duplicate reads if boundaries are unchecked.
  • Write clean, bug-free directional simulation loops without allocating extra visited arrays.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Any requirement to traverse a 2D matrix along its boundary or in a concentric inward spiral.
  • Problems involving directional simulation (Right -> Down -> Left -> Up).
  • Need for constant O(1) auxiliary memory without allocating a boolean visited matrix.

Algorithmic Decision Tree:

  • When spiraling through a 2D grid: Define four bounding pointers (top, bottom, left, right) and shrink them after completing each directional leg.
  • If the grid can have non-equal dimensions (m != n): Always re-check boundary conditions (top <= bottom and left <= right) before executing the third (Left) and fourth (Up) legs.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Visited Matrix Direction Simulation (Brute Force)

Intuition

Maintain current position (r, c) and direction pointer (dr, dc) cycling through right (0, 1), down (1, 0), left (0, -1), up (-1, 0). Before moving, check if the next cell is out of bounds or already visited. If so, rotate direction 90 degrees clockwise.

When to apply: Use to understand state machine direction turning on 2D grids.

Direction Simulation Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current operationSTEP 1 OF 6
Matrix 3x3
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
↑ (0,0)
2
3
r1
4
5
6
r2
7
8
9
Variables at this step
r
0
c
0
dir
RIGHT
spiral
[1]
Check / comparison
Cell (0, 0) = 1
Decision / next transition
Mark (0, 0) visited. Advance right.
Why this step matters

Matrix 3x3. Start at (0, 0) facing RIGHT. Add 1 to spiral.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public List<Integer> spiralOrder(int[][] matrix) {
6 List<Integer> res = new ArrayList<>();
7 if (matrix == null || matrix.length == 0) return res;
8 int m = matrix.length, n = matrix[0].length;
9 boolean[][] visited = new boolean[m][n];
10 int[] dr = {0, 1, 0, -1};
11 int[] dc = {1, 0, -1, 0};
12 int r = 0, c = 0, di = 0;
13
14 for (int i = 0; i < m * n; i++) {
15 res.add(matrix[r][c]);
16 visited[r][c] = true;
17 int cr = r + dr[di];
18 int cc = c + dc[di];
19 if (cr >= 0 && cr < m && cc >= 0 && cc < n && !visited[cr][cc]) {
20 r = cr;
21 c = cc;
22 } else {
23 di = (di + 1) % 4;
24 r += dr[di];
25 c += dc[di];
26 }
27 }
28 return res;
29 }
30 }
31
32 public static void main(String[] args) {
33 Solution sol = new Solution();
34 int[][] matrix = {
35 {1, 2, 3},
36 {4, 5, 6},
37 {7, 8, 9}
38 };
39 System.out.println("Spiral Order: " + sol.spiralOrder(matrix));
40 }
41}

Time & Space Complexity

  • Time complexity: O(m * n) — Visits every cell exactly once, doing O(1) checks per step.
  • Space complexity: O(m * n) — O(m * n) auxiliary 2D boolean matrix to store visited states.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Concentric Layer Peeling (Better)

Intuition

A matrix can be decomposed into concentric rings. For layer k (0 <= k < min(m, n)/2), traverse the top boundary, right boundary, bottom boundary, and left boundary of the k-th ring. Handles non-square matrices by checking remaining dimensions.

When to apply: Use to understand geometric ring-by-ring recursive perimeter decomposition.

Concentric Layer Peeling Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current operationSTEP 1 OF 6
Layer 0: Outer ring
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
↑ Layer 0 Top
2
3
r1
4
5
6
r2
7
8
9
Variables at this step
layer
0
spiral
[1,2,3]
Check / comparison
Process outer perimeter.
Decision / next transition
Add 1, 2, 3 to spiral.
Why this step matters

Layer 0: Outer ring. Top row: [1, 2, 3].

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public List<Integer> spiralOrder(int[][] matrix) {
6 List<Integer> res = new ArrayList<>();
7 if (matrix == null || matrix.length == 0) return res;
8 int r1 = 0, r2 = matrix.length - 1;
9 int c1 = 0, c2 = matrix[0].length - 1;
10 while (r1 <= r2 && c1 <= c2) {
11 for (int c = c1; c <= c2; c++) res.add(matrix[r1][c]);
12 for (int r = r1 + 1; r <= r2; r++) res.add(matrix[r][c2]);
13 if (r1 < r2 && c1 < c2) {
14 for (int c = c2 - 1; c > c1; c--) res.add(matrix[r2][c]);
15 for (int r = r2; r > r1; r--) res.add(matrix[r][c1]);
16 }
17 r1++;
18 r2--;
19 c1++;
20 c2--;
21 }
22 return res;
23 }
24 }
25
26 public static void main(String[] args) {
27 Solution sol = new Solution();
28 int[][] matrix = {
29 {1, 2, 3},
30 {4, 5, 6},
31 {7, 8, 9}
32 };
33 System.out.println("Spiral Order: " + sol.spiralOrder(matrix));
34 }
35}

Time & Space Complexity

  • Time complexity: O(m * n) — Every cell is added to the result exactly once.
  • Space complexity: O(1) auxiliary — O(1) memory outside the result list.

3. 4-Boundary Inward Shrink (Optimal)

Intuition

1. Define four bounds: top = 0, bottom = m - 1, left = 0, right = n - 1. 2. Traverse from left to right along top boundary; top++. 3. Traverse from top to bottom along right boundary; right--. 4. If top <= bottom, traverse from right to left along bottom boundary; bottom--. 5. If left <= right, traverse from bottom to top along left boundary; left++. Repeat until boundaries cross.

When to apply: Use as the clean, standard optimal solution for spiral matrix traversal.

4-Boundary Inward Shrink Interactive Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current operationSTEP 1 OF 6
Step 1: Bounds: top=0, bottom=2, left=0, right=2
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
↑ Top row
2
3
r1
4
5
6
r2
7
8
9
Variables at this step
top
1
bottom
2
left
0
right
2
spiral
[1,2,3]
Check / comparison
Traverse top row: 1, 2, 3
Decision / next transition
top becomes 1. Bounds: top=1, bottom=2, left=0, right=2.
Why this step matters

Step 1: Bounds: top=0, bottom=2, left=0, right=2. Traverse top row: col 0 to 2 -> values [1, 2, 3]. Shrink top = 1.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public List<Integer> spiralOrder(int[][] matrix) {
6 List<Integer> res = new ArrayList<>();
7 if (matrix == null || matrix.length == 0) return res;
8 int top = 0, bottom = matrix.length - 1;
9 int left = 0, right = matrix[0].length - 1;
10
11 while (top <= bottom && left <= right) {
12 for (int c = left; c <= right; c++) res.add(matrix[top][c]);
13 top++;
14
15 for (int r = top; r <= bottom; r++) res.add(matrix[r][right]);
16 right--;
17
18 if (top <= bottom) {
19 for (int c = right; c >= left; c--) res.add(matrix[bottom][c]);
20 bottom--;
21 }
22
23 if (left <= right) {
24 for (int r = bottom; r >= top; r--) res.add(matrix[r][left]);
25 left++;
26 }
27 }
28 return res;
29 }
30 }
31
32 public static void main(String[] args) {
33 Solution sol = new Solution();
34 int[][] matrix = {
35 {1, 2, 3},
36 {4, 5, 6},
37 {7, 8, 9}
38 };
39 System.out.println("Spiral Order: " + sol.spiralOrder(matrix));
40 }
41}

Time & Space Complexity

  • Time complexity: O(m * n) — Every cell in the m x n grid is visited exactly once.
  • Space complexity: O(1) auxiliary — O(1) auxiliary memory outside the result list.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Visited Matrix Simulation (State Machine)O(M * N)O(M * N)Simulate step-by-step movement using direction vectors (dx, dy) and an auxiliary visited boolean grid.Repeated redundant scans over the input.
2.Approach 2: Direction Vectors with Dynamic Boundary Turns (O(1) Space)O(M * N)O(1)Simulate movement using direction vectors and step counters along each axis without a visited matrix.Auxiliary memory allocation or sorting step.
3.Approach 3: 4-Boundary Inward Shrink (Optimal & Standard)OptimalO(M * N)O(1)Maintain four pointers (top, bottom, left, right) that shrink inward layer by layer.None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • 1 x N Single Row Matrix [[1, 2, 3, 4]] — Input: `, Expected: ` —
  • N x 1 Single Column Matrix [[1], [2], [3], [4]] — Input: `, Expected: ` —
  • 1 x 1 Single Cell Matrix [[42]] — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Spiral Matrix?

2.Why is the brute force approach suboptimal for large inputs in Spiral Matrix?

3.Which data structure or technique enables the optimal solution for Spiral Matrix?

Back to DSA Sheet