Problem overview
The method spiralOrder takes a matrix, a vector<vector<int>> with m rows and n columns, and returns a vector<int> with all its elements in spiral order. The spiral starts at the top-left corner and goes clockwise around the outside: 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. Then it repeats on the part that is left inside, until every element has been visited exactly once.
For this matrix:
1 2 3
4 5 6
7 8 9
the result is [1, 2, 3, 6, 9, 8, 7, 4, 5]. The outside ring gives 1, 2, 3, 6, 9, 8, 7, 4, and only 5 is left in the middle. The matrix doesn't have to be square: a 3 by 4 matrix gives [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7], where the inside that remains after one lap is a single row, 6 and 7.
Approach: four boundaries that move inward
There is no clever formula here. The task is to simulate the walk without losing track of where you are. Keeping a grid of "visited" flags and turning right at every wall works, but it needs O(m * n) extra memory for the flags.
A simpler way is to remember the part of the matrix that hasn't been visited yet, as a rectangle with four boundaries: top and bottom are the first and last unvisited rows, left and right the first and last unvisited columns. One lap walks the four sides of that rectangle. After each side is finished, its boundary moves one step inward. When the boundaries cross, nothing is left.
Every element is added exactly once, so the time is O(m * n), and apart from the result vector the extra space is a few integers.
The one subtle point is the end of the walk. When the rectangle has shrunk to a single row or a single column, the first two sides already cover everything. Walking the other two would add the same elements again. That is why the last two sides each sit behind an if.
Step by step
- Create an empty
vector<int>namedresultthat collects elements in the order they are visited. - Declare
topas 0 andbottomasmatrix.size() - 1, bothint. At the start every row is unvisited. - Declare
leftas 0 andrightasmatrix[0].size() - 1. Every row has the same length, so row 0 tells the column count. - Loop while
top <= bottom && left <= right. As long as neither pair has crossed, some elements remain. Each pass is one lap. - Walk the top row with
colfromlefttoright, both ends included, addingmatrix[top][col]withpush_back. - Move
topdown:top++. The top row is done. Doing this now also keeps the top-right corner from being visited again by the next side. - Walk the right column with
rowfromtop(already moved) tobottom, addingmatrix[row][right]. - Move
rightleft:right--. - Check
top <= bottom. If only one row was left, it was just walked as the top row, and going back along it would repeat its elements. - Inside that
if, walk the bottom row backwards withcolfromrightdown toleft, addingmatrix[bottom][col], then dobottom--. - Check
left <= right. If only one column was left, it was just walked as the right column. - Inside that
if, walk the left column upwards withrowfrombottomdown totop, addingmatrix[row][left], then doleft++. - After the
whileloop, returnresult.
The solution in C++
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>> &matrix) {
vector<int> result;
int top = 0, bottom = matrix.size() - 1;
int left = 0, right = matrix[0].size() - 1;
while (top <= bottom && left <= right) {
for (int col = left; col <= right; col++) {
result.push_back(matrix[top][col]);
}
top++;
for (int row = top; row <= bottom; row++) {
result.push_back(matrix[row][right]);
}
right--;
if (top <= bottom) {
for (int col = right; col >= left; col--) {
result.push_back(matrix[bottom][col]);
}
bottom--;
}
if (left <= right) {
for (int row = bottom; row >= top; row--) {
result.push_back(matrix[row][left]);
}
left++;
}
}
return result;
}
};
The C++ details worth knowing:
size()is unsigned, the boundaries are not.matrix.size() - 1is computed as an unsigned number and then converted when it is stored in anint. For a non-empty matrix that is the ordinary last index. Keepingtop,bottom,leftandrightas signedints matters, because the boundaries can step past each other:bottomcan reach -1, and a signed comparison liketop <= bottomthen correctly says "nothing left". An unsignedbottomwould wrap to a huge number instead.push_backgrows the vector.resultstarts empty and gains one element per call, so you never index into it.- Declaring several variables on one line.
int top = 0, bottom = matrix.size() - 1;declares two separateints, each with its own initial value. matrix[0]needs a non-empty matrix. The constraints guarantee at least one row and one column, so readingmatrix[0].size()is safe here.
Edge cases and common mistakes
- A single row.
{{1, 2, 3}}gives[1, 2, 3]. After the top row,topis 1 andbottomis 0, so the bottom-rowifis skipped. - A single column.
{{3}, {2}, {1}}gives[3, 2, 1]. After the right column,rightis -1 andleftis 0, so the left-columnifis skipped. - A single element.
{{4}}gives[4]. - A non-square matrix.
{{1, 2}, {3, 4}, {5, 6}}gives[1, 2, 4, 6, 5, 3]. - Leaving out the two
ifchecks. This is the classic mistake. Without them, the 3 by 4 example returns[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7, 6], with 6 repeated. The single column example returns[3, 2, 1, 2], and the single row returns[1, 2, 3, 2, 1]. - Updating a boundary after its side is walked, but in the wrong place. If
top++comes after the right column instead of before it, the top-right corner is added twice. - Using
col < rightinstead ofcol <= right. Both boundaries are rows or columns that still hold unvisited elements, so both ends are included.
Complexity
Time is O(m * n). Each element is pushed exactly once, and the checks and boundary moves cost O(1) per lap, with at most about min(m, n) / 2 laps.
Extra space is O(1) apart from result, which holds all m * n elements because it is the output.
