Spiral Matrix

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.

Q: 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.

Medium Simulation

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

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. The loop continues while the left boundary is less than the right and the top boundary is less than the bottom, ensuring all elements are covered exactly once.

Optimal Approach

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.

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.

Pattern Spotlight

Simulation (Boundary Shrinking)

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.

Solution

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

1import java.util.ArrayList;
2import java.util.List;
3
4public class Solution {
  public List<Integer> spiralOrder(int[][] matrix) {
      List<Integer> res = new ArrayList<>();
      int left = 0, right = matrix[0].length;
      int top = 0, bottom = matrix.length;
9
      while (left < right && top < bottom) {
          for (int i = left; i < right; i++) {
              res.add(matrix[top][i]);
          }
          top++;
15
          for (int i = top; i < bottom; i++) {
              res.add(matrix[i][right - 1]);
          }
          right--;
20
          if (!(left < right && top < bottom)) {
              break;
          }
24
          for (int i = right - 1; i >= left; i--) {
              res.add(matrix[bottom - 1][i]);
          }
          bottom--;
29
          for (int i = bottom - 1; i >= top; i--) {
              res.add(matrix[i][left]);
          }
          left++;
      }
35
      return res;
  }
38}

1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    vector<int> spiralOrder(vector<vector<int>>& matrix) {
7        vector<int> res;
8        int left = 0, right = matrix[0].size();
9        int top = 0, bottom = matrix.size();
10
11        while (left < right && top < bottom) {
12            for (int i = left; i < right; i++) {
13                res.push_back(matrix[top][i]);
14            }
15            top++;
16
17            for (int i = top; i < bottom; i++) {
18                res.push_back(matrix[i][right - 1]);
19            }
20            right--;
21
22            if (!(left < right && top < bottom)) {
23                break;
24            }
25
26            for (int i = right - 1; i >= left; i--) {
27                res.push_back(matrix[bottom - 1][i]);
28            }
29            bottom--;
30
31            for (int i = bottom - 1; i >= top; i--) {
32                res.push_back(matrix[i][left]);
33            }
34            left++;
35        }
36
37        return res;
38    }
39};

1var spiralOrder = function(matrix) {
  const res = [];
  let left = 0, right = matrix[0].length;
  let top = 0, bottom = matrix.length;
5
  while (left < right && top < bottom) {
      for (let i = left; i < right; i++) {
          res.push(matrix[top][i]);
      }
      top++;
11
      for (let i = top; i < bottom; i++) {
          res.push(matrix[i][right - 1]);
      }
      right--;
16
      if (!(left < right && top < bottom)) {
          break;
      }
20
      for (let i = right - 1; i >= left; i--) {
          res.push(matrix[bottom - 1][i]);
      }
      bottom--;
25
      for (let i = bottom - 1; i >= top; i--) {
          res.push(matrix[i][left]);
      }
      left++;
  }
31
  return res;
33};

Step-by-Step Solution

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.

Traverse Top Row and Shrink Top Boundary

7while left < right and top < bottom:
  for i in range(left, right):
      res.append(matrix[top][i])
  top += 1

Objective

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

Key Insight

Traversing the top row from left to right covers the current upper edge of the submatrix. Incrementing the top boundary after this traversal excludes the visited row from future iterations, preventing duplicates and ensuring progress.

Interview Quick-Check

Core Logic

Iterate over columns from left to right within current boundaries to collect the top row elements.

State & Boundaries

Increment top boundary after traversal to exclude the visited row.

Traverse Right Column and Shrink Right Boundary

12for i in range(top, bottom):
13    res.append(matrix[i][right - 1])
14right -= 1

Objective

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

Key Insight

Traversing the right column covers the current right edge of the submatrix. Decrementing the right boundary after traversal excludes the visited column, maintaining the shrinking spiral pattern and preventing revisits.

Interview Quick-Check

Core Logic

Iterate over rows from top to bottom within current boundaries to collect the right column elements.

State & Boundaries

Decrement right boundary after traversal to exclude the visited column.

Check Boundaries Before Bottom and Left Traversals

16if not (left < right and top < bottom):
17    break

Objective

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

Key Insight

After shrinking the top and right boundaries, the submatrix might be empty or invalid. This check prevents out-of-bounds access and duplicate visits by ensuring that the left boundary is still less than the right and the top is less than the bottom before proceeding.

Interview Quick-Check

Core Logic

Boundary check prevents invalid traversal and duplicate element visits.

Common Pitfalls & Bugs

Skipping this check can cause index errors or duplicate entries in the result.

Traverse Bottom Row and Shrink Bottom Boundary

19for i in range(right - 1, left - 1, -1):
20    res.append(matrix[bottom - 1][i])
21bottom -= 1

Objective

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

Key Insight

Traversing the bottom row in reverse order covers the current bottom edge of the submatrix. Decrementing the bottom boundary after traversal excludes the visited row, continuing the spiral inward and preventing revisits.

Interview Quick-Check

Core Logic

Iterate over columns from right to left within current boundaries to collect the bottom row elements.

State & Boundaries

Decrement bottom boundary after traversal to exclude the visited row.

Traverse Left Column and Shrink Left Boundary

23for i in range(bottom - 1, top - 1, -1):
24    res.append(matrix[i][left])
25left += 1

Objective

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

Key Insight

Traversing the left column in reverse order covers the current left edge of the submatrix. Incrementing the left boundary after traversal excludes the visited column, completing one full spiral layer and preparing for the next iteration.

Interview Quick-Check

Core Logic

Iterate over rows from bottom to top within current boundaries to collect the left column elements.

State & Boundaries

Increment left boundary after traversal to exclude the visited column.

Return the Accumulated Spiral Order Result

27	`return res`

Objective

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

Key Insight

After the while loop terminates, all elements have been visited exactly once in spiral order. Returning the accumulated list provides the final answer as required by the problem.

Interview Quick-Check

Core Logic

Return the result list containing the spiral traversal of the matrix.

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.

Line 10 Core

top += 1

Move the top boundary down to exclude the visited row.

Incrementing top ensures the next iteration does not revisit the already traversed top row, maintaining correctness and progress.

Line 14 Core

right -= 1

Move the right boundary left to exclude the visited column.

Decrementing right ensures the next iteration does not revisit the already traversed right column, maintaining correctness and progress.

Line 17 Core

break

Break the loop if the submatrix is invalid.

Exiting early prevents unnecessary or invalid traversals, ensuring the algorithm terminates correctly once all elements are visited.

Line 21 Core

bottom -= 1

Move the bottom boundary up to exclude the visited row.

Decrementing bottom ensures the next iteration does not revisit the already traversed bottom row, maintaining correctness and progress.

Line 25 Core

left += 1

Move the left boundary right to exclude the visited column.

Incrementing left ensures the next iteration does not revisit the already traversed left column, maintaining correctness and progress.

Line 8 Core

for i in range(left, right):

Iterate over columns from left to right along the top row.

This loop collects all elements in the current top row within the current boundaries, forming the first edge of the spiral layer.

Line 9 Core

res.append(matrix[top][i])

Append the current top row element to the result list.

Adding elements in left-to-right order preserves the spiral traversal sequence for the top edge.

Line 12 Core

for i in range(top, bottom):

Iterate over rows from top to bottom along the rightmost column.

This loop collects all elements in the current right column within the current boundaries, forming the second edge of the spiral layer.

Line 13 Core

res.append(matrix[i][right - 1])

Append the current right column element to the result list.

Adding elements in top-to-bottom order preserves the spiral traversal sequence for the right edge.

Line 19 Core

for i in range(right - 1, left - 1, -1):

Iterate over columns from right to left along the bottom row.

This loop collects all elements in the current bottom row within the current boundaries in reverse order, forming the third edge of the spiral layer.

Line 20 Core

res.append(matrix[bottom - 1][i])

Append the current bottom row element to the result list.

Adding elements in right-to-left order preserves the spiral traversal sequence for the bottom edge.

Line 23 Core

for i in range(bottom - 1, top - 1, -1):

Iterate over rows from bottom to top along the leftmost column.

This loop collects all elements in the current left column within the current boundaries in reverse order, forming the fourth edge of the spiral layer.

Line 24 Core

res.append(matrix[i][left])

Append the current left column element to the result list.

Adding elements in bottom-to-top order preserves the spiral traversal sequence for the left edge.

Line 7 Standard

while left < right and top < bottom:

Begin the main loop that continues while the submatrix is valid.

The loop condition ensures traversal continues only while there is a valid submatrix to process, preventing out-of-bounds access.

Line 4 Standard

left, right = 0, len(matrix[0])

Set the left and right boundaries for columns.

Left starts at 0, and right is set to the number of columns, representing an exclusive upper bound for column indices in the current submatrix.

Line 5 Standard

top, bottom = 0, len(matrix)

Set the top and bottom boundaries for rows.

Top starts at 0, and bottom is set to the number of rows, representing an exclusive upper bound for row indices in the current submatrix.

Line 27 Standard

return res

Return the list of elements collected in spiral order.

After completing the traversal, the result list contains all matrix elements in the required spiral sequence, fulfilling the problem's output specification.

Line 3 Basic

res = []

Initialize an empty list to store the spiral order elements.

This list accumulates the matrix elements in the order they are visited, enabling a clean return of the final spiral sequence.

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?

Because after shrinking the top and right boundaries, the remaining submatrix might be empty or invalid, and traversing the bottom or left edges without this check could cause duplicate visits or index errors. The boundary check ensures that each element is visited exactly once.

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`

1	`import java.util.ArrayList;`
2	`import java.util.List;`
3
4	`public class Solution {`
5	`public List<Integer> spiralOrder(int[][] matrix) {`
6	`List<Integer> res = new ArrayList<>();`
7	`int left = 0, right = matrix[0].length;`
8	`int top = 0, bottom = matrix.length;`
9
10	`while (left < right && top < bottom) {`
11	`for (int i = left; i < right; i++) {`
12	`res.add(matrix[top][i]);`
13	`}`
14	`top++;`
15
16	`for (int i = top; i < bottom; i++) {`
17	`res.add(matrix[i][right - 1]);`
18	`}`
19	`right--;`
20
21	`if (!(left < right && top < bottom)) {`
22	`break;`
23	`}`
24
25	`for (int i = right - 1; i >= left; i--) {`
26	`res.add(matrix[bottom - 1][i]);`
27	`}`
28	`bottom--;`
29
30	`for (int i = bottom - 1; i >= top; i--) {`
31	`res.add(matrix[i][left]);`
32	`}`
33	`left++;`
34	`}`
35
36	`return res;`
37	`}`
38	`}`

1	`#include <vector>`
2	`using namespace std;`
3
4	`class Solution {`
5	`public:`
6	`vector<int> spiralOrder(vector<vector<int>>& matrix) {`
7	`vector<int> res;`
8	`int left = 0, right = matrix[0].size();`
9	`int top = 0, bottom = matrix.size();`
10
11	`while (left < right && top < bottom) {`
12	`for (int i = left; i < right; i++) {`
13	`res.push_back(matrix[top][i]);`
14	`}`
15	`top++;`
16
17	`for (int i = top; i < bottom; i++) {`
18	`res.push_back(matrix[i][right - 1]);`
19	`}`
20	`right--;`
21
22	`if (!(left < right && top < bottom)) {`
23	`break;`
24	`}`
25
26	`for (int i = right - 1; i >= left; i--) {`
27	`res.push_back(matrix[bottom - 1][i]);`
28	`}`
29	`bottom--;`
30
31	`for (int i = bottom - 1; i >= top; i--) {`
32	`res.push_back(matrix[i][left]);`
33	`}`
34	`left++;`
35	`}`
36
37	`return res;`
38	`}`
39	`};`

1	`var spiralOrder = function(matrix) {`
2	`const res = [];`
3	`let left = 0, right = matrix[0].length;`
4	`let top = 0, bottom = matrix.length;`
5
6	`while (left < right && top < bottom) {`
7	`for (let i = left; i < right; i++) {`
8	`res.push(matrix[top][i]);`
9	`}`
10	`top++;`
11
12	`for (let i = top; i < bottom; i++) {`
13	`res.push(matrix[i][right - 1]);`
14	`}`
15	`right--;`
16
17	`if (!(left < right && top < bottom)) {`
18	`break;`
19	`}`
20
21	`for (let i = right - 1; i >= left; i--) {`
22	`res.push(matrix[bottom - 1][i]);`
23	`}`
24	`bottom--;`
25
26	`for (let i = bottom - 1; i >= top; i--) {`
27	`res.push(matrix[i][left]);`
28	`}`
29	`left++;`
30	`}`
31
32	`return res;`
33	`};`

7	`while left < right and top < bottom:`
8	`for i in range(left, right):`
9	`res.append(matrix[top][i])`
10	`top += 1`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Boundaries and Result Container

Traverse Top Row and Shrink Top Boundary

Traverse Right Column and Shrink Right Boundary

Check Boundaries Before Bottom and Left Traversals

Traverse Bottom Row and Shrink Bottom Boundary

Traverse Left Column and Shrink Left Boundary

Return the Accumulated Spiral Order Result

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.