Spiral Matrix
Problem Statement
Given an m x n matrix, return all elements of the matrix in spiral order.
Constraints:
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 10
- -100 <= matrix[i][j] <= 100
Input Format:
- An m x n matrix
Output Format:
- Return all elements of the matrix in spiral order as an array
Examples:
Example 1:
Input:
matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output:
[1,2,3,6,9,8,7,4,5]
Explanation:
Starting from the top-left corner, we traverse in a clockwise spiral: right along the first row, down along the last column, left along the last row, up along the first column, and finally right along the second row.
Example 2:
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:
Spiral traversal of the matrix follows the pattern: right, down, left, up, right, etc.
Solutions
Layer by Layer Approach
Traverse the matrix in a spiral order by processing each "layer" of the matrix, starting from the outermost layer and moving inward.
Direction-Based Approach
Use a direction variable to keep track of the current direction (right, down, left, up) and change direction when we hit a boundary or a visited cell.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Initialize: top=0, right=2, bottom=2, left=0, result=[]
- Traverse right (top=0): Add matrix[0][0]=1, matrix[0][1]=2, matrix[0][2]=3 to result. result=[1,2,3], top=1
- Traverse down (right=2): Add matrix[1][2]=6, matrix[2][2]=9 to result. result=[1,2,3,6,9], right=1
- Traverse left (bottom=2): Add matrix[2][1]=8, matrix[2][0]=7 to result. result=[1,2,3,6,9,8,7], bottom=1
- Traverse up (left=0): Add matrix[1][0]=4 to result. result=[1,2,3,6,9,8,7,4], left=1
- Traverse right (top=1): Add matrix[1][1]=5 to result. result=[1,2,3,6,9,8,7,4,5]
- All elements have been traversed. Return result=[1,2,3,6,9,8,7,4,5]
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the spiral traversal of the matrix, highlighting the current position and the path taken.
Key visualization elements:
- current position
- traversed path
- boundaries
Implementation Notes
This problem tests your ability to manipulate a 2D matrix and track boundaries. The key insight is to process the matrix layer by layer in a spiral pattern, carefully handling the boundary conditions to avoid duplicating elements.