DSA
Spiral Matrix
Simulation approach.
Practice here Given an m x n matrix, return all elements of the matrix in spiral order.
Simulation#
- Intuition: Traversing a matrix in spiral order means repeatedly peeling the outermost layer: go right along the top row, down the right column, left along the bottom row, and up the left column — then shrink the boundary inward and repeat until all elements are visited.
- Mechanics: Four boundary variables (top, bottom, left, right) define the current unvisited rectangle. Each of the four directional passes shrinks the corresponding boundary by one after completing, and the loop terminates early via break when two opposite boundaries meet (the rectangle collapses to a single row, column, or point).
- Trade-off: O(m×n) time — every element is visited exactly once. O(1) auxiliary space beyond the output vector. The boundary-shrinking approach is straightforward to implement correctly and handles non-square matrices and degenerate cases (single row/column) without special-casing.
cpp
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> result;
int top = 0, bottom = matrix.size();
int left = 0, right = matrix[0].size();
while(true){
//top row
for(int i=left;i<right;i++){
result.push_back(matrix[top][i]);
}
top++;
if(top==bottom)
break;
//right column
for(int i=top;i<bottom;i++){
result.push_back(matrix[i][right-1]);
}
right--;
if(right==left)
break;
//bottom row
for(int i=right;i>left;i--){
result.push_back(matrix[bottom-1][i-1]);
}
bottom--;
if(bottom==top)
break;
//left col
for(int i=bottom;i>top;i--){
result.push_back(matrix[i-1][left]);
}
left++;
if(left==right)
break;
}
return result;
}
};