How do you solve Spiral Matrix?

Use four pointers to represent the current boundaries of the unvisited submatrix. Traverse the top row from left to right, then increment the top boundary. Traverse the right column from top to bottom, then decrement the right boundary. Check if boundaries still allow traversal; if so, traverse the bottom row from right to left, then decrement the bottom boundary. Finally, traverse the left column from bottom to top, then increment the left boundary. Repeat until all elements are visited. This approach runs in O(m*n) time and uses O(1) auxiliary space.

What pattern does Spiral Matrix use?

The Pattern: Simulation (Boundary Shrinking) The Heuristic: When traversing a matrix in a complex pattern like spiral order, maintain explicit boundary pointers and simulate each directional traversal step-by-step, shrinking boundaries after each pass to avoid revisiting elements and to control the traversal space.

Spiral Matrix — Simulation

Q: What is the time complexity of Spiral Matrix?

O(m * n). Each element of the matrix is visited exactly once during the traversal, and each boundary pointer is updated at most O(m + n) times, resulting in linear time proportional to the number of elements.

Problem

Given an m x n matrix, return all elements of the matrix in spiral order.

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 10⁴
−10⁵ ≤ matrix[i][j] ≤ 10⁵

Example

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output: [1,2,3,6,9,8,7,4,5]

The traversal begins at the top row moving right: 1, 2, 3. Then moves down the last column: 6, 9. Then moves left along the bottom row: 8, 7. Then moves up the first column: 4. After completing the outer layer, the boundaries shrink inward, and the process repeats for the inner submatrix, visiting 5 last.

Approach

Straightforward Solution

A naive approach might attempt to simulate the spiral by tracking visited cells and directions, but this requires extra space and complex state management. Alternatively, a brute-force approach could attempt to reconstruct the spiral by repeatedly slicing rows and columns, but this is inefficient and error-prone.

Core Observation

The spiral traversal can be viewed as repeatedly traversing the outer perimeter of the current submatrix, then shrinking the boundaries inward. Each iteration visits the top row left-to-right, the right column top-to-bottom, the bottom row right-to-left, and the left column bottom-to-top, adjusting boundaries after each pass.

Path to Optimal

Preview

The key insight is to maintain four pointers representing the current boundaries: left, right, top, and bottom. By iterating over these boundaries in order and shrinking them after each traversal, the algorithm simulates the spiral without extra space for visited flags…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use four pointers to represent the current boundaries of the unvisited submatrix. Traverse the top row from left to right, then increment the top boundary…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

Each element of the matrix is visited exactly once during the traversal, and each boundary pointer is updated at most O(m + n) times, resulting in linear time proportional to the number of elements.

Space

O(1)

The algorithm uses only a fixed number of integer variables to track boundaries and the result list for output, which is required by the problem and not counted as auxiliary space.

Solution

Python

1class Solution:
  def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
      res = []
      left, right = 0, len(matrix[0])
      top, bottom = 0, len(matrix)
6
      while left < right and top < bottom:
          for i in range(left, right):
              res.append(matrix[top][i])
          top += 1
11
          for i in range(top, bottom):
              res.append(matrix[i][right - 1])
          right -= 1
15
          if not (left < right and top < bottom):
              break
          
          for i in range(right - 1, left - 1, -1):
              res.append(matrix[bottom - 1][i])
          bottom -= 1
22
          for i in range(bottom - 1, top - 1, -1):
              res.append(matrix[i][left])
          left += 1
      
      return res

Step-by-Step Solution

1

Initialize Boundaries and Result Container

3res = []
4left, right = 0, len(matrix[0])
5top, bottom = 0, len(matrix)

Objective

To set up the initial boundaries of the matrix and prepare the list to accumulate the spiral order elements.

Key Insight

Defining the left, right, top, and bottom boundaries as indices allows the algorithm to simulate the shrinking spiral layer by layer. The result list collects elements in the order they are visited, enabling a clean return of the final spiral sequence.

Interview Quick-Check

Core Logic

The boundaries represent the current unvisited submatrix edges, enabling controlled traversal without revisiting elements.

State & Boundaries

Initialize right as len(matrix[0]) and bottom as len(matrix) to represent exclusive upper bounds for columns and rows.

2

Traverse Top Row and Shrink Top Boundary

To collect elements from the top row moving left to right and then move the top boundary inward.

3

Traverse Right Column and Shrink Right Boundary

To collect elements from the rightmost column moving top to bottom and then move the right boundary inward.

4

Check Boundaries Before Bottom and Left Traversals

To verify that the remaining submatrix is valid before traversing the bottom row and left column.

5

Traverse Bottom Row and Shrink Bottom Boundary

To collect elements from the bottom row moving right to left and then move the bottom boundary inward.

6

Traverse Left Column and Shrink Left Boundary

To collect elements from the leftmost column moving bottom to top and then move the left boundary inward.

7

Return the Accumulated Spiral Order Result

To return the list containing all matrix elements in spiral order after traversal completion.

6 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 16 Critical

if not (left < right and top < bottom):

Check if the submatrix is still valid before traversing bottom and left edges.

This check is critical to avoid revisiting elements or accessing invalid indices after shrinking the top and right boundaries, preserving correctness and preventing runtime errors.

Full line-by-line criticality + rationale for all 19 lines available on Pro.

Test Your Understanding

Why must the algorithm check the boundary conditions after traversing the top and right edges before proceeding to the bottom and left edges?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Spiral Matrix from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Spiral Matrix drill

or drill a free problem

1	`class Solution:`
2	`def spiralOrder(self, matrix: list[list[int]]) -> list[int]:`
3	`res = []`
4	`left, right = 0, len(matrix[0])`
5	`top, bottom = 0, len(matrix)`
6
7	`while left < right and top < bottom:`
8	`for i in range(left, right):`
9	`res.append(matrix[top][i])`
10	`top += 1`
11
12	`for i in range(top, bottom):`
13	`res.append(matrix[i][right - 1])`
14	`right -= 1`
15
16	`if not (left < right and top < bottom):`
17	`break`
18
19	`for i in range(right - 1, left - 1, -1):`
20	`res.append(matrix[bottom - 1][i])`
21	`bottom -= 1`
22
23	`for i in range(bottom - 1, top - 1, -1):`
24	`res.append(matrix[i][left])`
25	`left += 1`
26
27	`return res`