Spiral Matrix
Asked at Apple, Databricks, Oracle, Walmart
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.
Asked At
| 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 → |
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.
Visual walkthrough for a 3x4 matrix:
1 2 3 4 / 5 6 7 8 / 9 10 11 12
top=0, bottom=2, left=0, right=3
- Left to right (top row): 1,2,3,4. top=1.
- Top to bottom (right col): 8,12. right=2.
- Right to left (bottom row): 11,10,9. bottom=1.
- Bottom to top (left col): 5. left=1.
- Now top=1, bottom=1, left=1, right=2.
- Left to right: 6,7. top=2. top > bottom, stop.
Result: [1,2,3,4,8,12,11,10,9,5,6,7]
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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Spiral Matrix?
Spiral Matrix is asked at Apple, Databricks, Oracle, Walmart. 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.