54. Spiral Matrix
Asked at Apple, Databricks, Oracle, Walmart and 2 more
Difficulty
Medium
Time
O(m*n)
Space
O(1)
Pattern
Array
Companies
6
Problem
You are given a 2D matrix with m rows and n columns. Return a single list that contains every element of the matrix, read in spiral order.
Spiral order means: start at the top-left corner, walk left to right along the top row, then top to bottom down the right column, then right to left along the bottom row, then bottom to top up the left column. That finishes one outer ring. Then move one step inward and repeat the same four moves on the smaller ring. Keep going until every cell has been read.
Each element must appear exactly once, and the order is always clockwise. The matrix may be square or rectangular, and it may have only one row or only one column.
Read the matrix in a clockwise spiral
Constraints
- ●
m == matrix.length - ●
n == matrix[i].length - ●
1 <= m, n <= 10 - ●
-100 <= matrix[i][j] <= 100
Examples
matrix = [[1,2,3],[4,5,6],[7,8,9]][1,2,3,6,9,8,7,4,5]matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]][1,2,3,4,8,12,11,10,9,5,6,7]Asked At
6 companies| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| Databricks | Medium | View all Databricks questions → |
| Oracle | Medium | View all Oracle questions → |
| Walmart | Medium | View all Walmart questions → |
| Bloomberg | Medium | View all Bloomberg questions → |
| TikTok | Medium | View all TikTok questions → |
How to Think About It
Key insight: define four boundaries -- top, bottom, left, right. Traverse the matrix in a spiral by: (1) left to right along the top, (2) top to bottom along the right, (3) right to left along the bottom, (4) bottom to top along the left. After each pass, shrink the corresponding boundary.
The boundary approach: start with top=0, bottom=m-1, left=0, right=n-1. After traversing the top row, increment top. After traversing the right column, decrement right. After traversing the bottom row, decrement bottom. After traversing the left column, increment left. Stop when boundaries cross.
Edge cases: single row (only traverse left to right, then right to left). single column (only traverse top to bottom, then bottom to top). single element. square matrix vs rectangular matrix.
Alternative approach: use a direction variable (0=right, 1=down, 2=left, 3=up) and a visited matrix. When you hit a boundary or visited cell, turn right. This is simpler but uses O(m*n) space for the visited matrix.
Optimal Approach
Step 1: Initialize boundaries: top=0, bottom=m-1, left=0, right=n-1.
Step 2: While top <= bottom and left <= right:
- Traverse left to right along top row. Increment top.
- Traverse top to bottom along right column. Decrement right.
- If top <= bottom: traverse right to left along bottom row. Decrement bottom.
- If left <= right: traverse bottom to top along left column. Increment left.
Walkthrough for [[1,2,3,4],[5,6,7,8],[9,10,11,12]]:
- top=0, bottom=2, left=0, right=3
- Row 0 L->R: 1,2,3,4. top=1.
- Col 3 T->B: 8,12. right=2.- Row 2 R->L: 11,10,9. bottom=1.
- Col 0 B->T: 5. left=1.
- top=1, bottom=1, left=1, right=2.
- Row 1 L->R: 6,7. top=2.
- top > bottom, stop.
- Result: [1,2,3,4,8,12,11,10,9,5,6,7]
Time: O(m*n) -- each element is visited exactly once. Space: O(1) excluding the output array.
Shrink four boundaries after each side
What Trips People Up in Real Interviews
Forgetting the bounds checks before traversing the bottom row and left column. After shrinking boundaries, top may exceed bottom or left may exceed right. Always check if top <= bottom before traversing the bottom row, and if left <= right before traversing the left column.
Not incrementing or decrementing the boundary after each traversal. If you forget top += 1 after the left-to-right pass, you will re-traverse the top row and get duplicate elements.
Using a direction variable with a visited matrix instead of the four-boundary approach. The boundary method uses O(1) extra space, while the visited approach uses O(m*n) space.
Confusing row and column indices when traversing. Left-to-right iterates columns (c), top-to-bottom iterates rows (r). Mixing them up causes index-out-of-bounds or wrong order.
Not handling single-row or single-column matrices. A single row needs only a left-to-right pass and a right-to-left pass. A single column needs top-to-bottom and bottom-to-top. The boundary checks handle this automatically if correct.
Solution Code
O(m*n) timedef spiralOrder(matrix):
if not matrix:
return []
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for c in range(left, right + 1):
result.append(matrix[top][c])
top += 1
for r in range(top, bottom + 1):
result.append(matrix[r][right])
right -= 1
if top <= bottom:
for c in range(right, left - 1, -1):
result.append(matrix[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1):
result.append(matrix[r][left])
left += 1
return resultFrequently Asked Questions
What is the Spiral Matrix problem?
Given an m x n matrix, return all elements of the matrix in spiral order (clockwise from the outer layer inward). This problem tests your ability to simulate traversal with boundary tracking.
How do you solve Spiral Matrix?
The optimal approach runs in O(m*n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Spiral Matrix?
Spiral Matrix is asked at Apple, Databricks, Oracle, Walmart, Bloomberg, TikTok. It is a medium difficulty problem.
What are common mistakes on Spiral Matrix?
- Forgetting the bounds checks before traversing the bottom row and left column. After shrinking boundaries, `top` may exceed `bottom` or `left` may exceed `right`. Always check `if top <= bottom` before traversing the bottom row, and `if left <= right` before traversing the left column.
- Not incrementing or decrementing the boundary after each traversal. If you forget `top += 1` after the left-to-right pass, you will re-traverse the top row and get duplicate elements.
- Using a `direction` variable with a `visited` matrix instead of the four-boundary approach. The boundary method uses `O(1)` extra space, while the visited approach uses `O(m*n)` space.
- Confusing row and column indices when traversing. Left-to-right iterates columns (`c`), top-to-bottom iterates rows (`r`). Mixing them up causes index-out-of-bounds or wrong order.
- Not handling single-row or single-column matrices. A single row needs only a left-to-right pass and a right-to-left pass. A single column needs top-to-bottom and bottom-to-top. The boundary checks handle this automatically if correct.