# Super Simple and Easy to Understand Solution

• This is a very simple and easy to understand solution. I traverse right and increment rowBegin, then traverse down and decrement colEnd, then I traverse left and decrement rowEnd, and finally I traverse up and increment colBegin.

The only tricky part is that when I traverse left or up I have to check whether the row or col still exists to prevent duplicates. If anyone can do the same thing without that check, please let me know!

``````public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {

List<Integer> res = new ArrayList<Integer>();

if (matrix.length == 0) {
return res;
}

int rowBegin = 0;
int rowEnd = matrix.length-1;
int colBegin = 0;
int colEnd = matrix[0].length - 1;

while (rowBegin <= rowEnd && colBegin <= colEnd) {
// Traverse Right
for (int j = colBegin; j <= colEnd; j ++) {
}
rowBegin++;

// Traverse Down
for (int j = rowBegin; j <= rowEnd; j ++) {
}
colEnd--;

if (rowBegin <= rowEnd) {
// Traverse Left
for (int j = colEnd; j >= colBegin; j --) {
}
}
rowEnd--;

if (colBegin <= colEnd) {
// Traver Up
for (int j = rowEnd; j >= rowBegin; j --) {
}
}
colBegin ++;
}

return res;
}
}``````

• This solution is excellent!! Thanks for sharing

• glad this helps! Happy leetcoding !

• Brilliant solution! I had the same idea but calculating depth + tail recursion.

• I used the same idea and I didn't check the condition in each while loop. Actually the maximum number can be computed. After all these loop, there are four conditions: done, one element left, one row left, one column left. and it's very straightforward to solve these conditions.

Although I used C++, it's very easy to understand the algorithm. Hope it helps.

`````` class Solution{
public:
vector<int> spiralOrder(vector<vector<int> > &matrix){
//create result vector
vector<int> result;

//get dimension of matrix
int m = matrix.size();
if (m==0)
return result;
int n = matrix[0].size();
if (n==0)  // empty matrix
return result;
result.resize(m*n);

int i, j, k=0; //(i, j): index of matrix; k: index of vector
int ly, ly_max; //ly: layer; ly_max: maximum layer
ly_max = (m>n)? (n/2):(m/2);
//traverse all elements
for(ly=0; ly<ly_max; ly++){
//from left to right: (k,k) -> (k, n-k-2), j++
i = ly; j=ly;
while(j < n-ly-1)
result[k++] = matrix[i][j++];

//from top to bottom: (k, n-k-1) -> (m-k-2, n-k-1), i++
j = n-ly-1;
while(i < m-ly-1)
result[k++] = matrix[i++][j];

//from right to left: (m-k-1, n-k-1) -> (m-k-1, k+1), j--
i = m-ly-1;
while(j > ly)
result[k++] = matrix[i][j--];

//from bottom to top: (m-k-1, k) -> (k+1, k), i--
j=ly;
while(i>ly)
result[k++] = matrix[i--][j];
}

// traverse left elements: one row or one column, or one element
if (m==n){
if (m%2==1)
result[k++] = matrix[ly_max][ly_max];
}
else if (m>n){
if (n%2==1) { //column
i = ly_max;
while(i<m-ly_max)
result[k++] = matrix[i++][ly_max];
}
}
else{
if (m%2==1){ //row
j = ly_max;
while(j<n-ly_max){
cout << j << ' ' << k << ' ' << matrix[ly_max][j] <<  endl;
result[k++] = matrix[ly_max][j++];
}
}
}
return result;
}
``````

};

• Thanks! happy to share :)

• I use tail recursion too and it can be easily transformed non-recursion.

• My cpp solution using same idea. state means direction and everything is just in code.

``````class Solution {
public:
vector<int> spiralOrder(vector<vector<int> > &matrix) {
int rows = matrix.size();
if (rows == 0) return vector<int> ();
int cols = matrix[0].size();
int row = 0, col = 0, layer = 0;
vector<int> res;
res.push_back(matrix[0][0]);
int state = 1;
for (int step = 1; step < rows * cols; step++) {
switch(state) { // based on state, check and change state, then move on
case 1: // supposed to go right
if (col == cols-layer-1) { // reach right bound
row++;
state = 2;
}
else col++;
break;
case 2: // supposed to go down
if (row == rows-layer-1) { // reach downside bound
col--;
state = 3;
}
else row++;
break;
case 3: // supposed to go left
if (col == layer) { // reach left bound
row--;
state = 4;
}
else col--;
break;
case 4: // supposed to go up
if (row == layer+1) { // reach upside bound
col++;
state = 1;
layer++;
}
else row--;
break;
}
res.push_back(matrix[row][col]);
}
return res;
}
};``````

• You should use an array of direction offsets if you want to be a game developer. And you don't need to check the border because rows and cols always decrease. Here is my C++ code:

``````class Solution {
public:
vector<int> spiralOrder(vector<vector<int>> &matrix) {
vector<int> result;
if (matrix.empty()) return result;
result = matrix[0];  // no need to check the first row
int dirs[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};  // direction offsets
int d = 0;  // direction index
int m = matrix.size();
int n = matrix[0].size();
int pos[2] = {0, n - 1};  // start from the top right corner
int i = (m - 1) * n;  // number of the rest numbers
while (i > 0) {
for (int j = 1; j < m; j++) {
i--;
pos[0] += dirs[d][0]; pos[1] += dirs[d][1];
result.push_back(matrix[pos[0]][pos[1]]);
}
m--;  // decrease the size of row or column
swap(m, n);  // switch between horizontal and vertical mode
d = (d + 1) % 4;  // loop between direction offsets
}
return result;
}
};
``````

• great idea, happy to know it, thanks.

• just return the correct list, and cut the duplicated items.

*return order[0:len(matrix)len(matrix[0])];

``````# @param matrix, a list of lists of integers
# @return a list of integers
def spiralOrder(self, matrix):
if(len(matrix)==0): return matrix;
order=[];

rb,re,cb,ce=0,len(matrix)-1,0,len(matrix[0])-1;
while(rb<=re and cb <=ce):
for i in range(cb,ce+1):
order.append(matrix[rb][i]);
rb+=1;

for i in range(rb,re+1):
order.append(matrix[i][ce]);
ce-=1;

for i in range(ce,cb-1,-1):
order.append(matrix[re][i]);
re-=1;

for i in range(re,rb-1,-1):
order.append(matrix[i][cb]);
cb+=1;

return order[0:len(matrix)*len(matrix[0])];``````

• Thanks for sharing!

• mine is almost the same, but more concise

``````vector<int> spiralOrder(vector<vector<int> > &matrix) {
vector<int> ans;
if (matrix.size() <= 0 || matrix[0].size() <= 0)
return ans;

int m = matrix.size(), n = matrix[0].size();
int x0 = 0, x1 = m - 1; // vertical
int y0 = 0, y1 = n - 1; // horizon

while(x0 <= x1 && y0 <= y1) {
// travel right side
for (int j = y0; j <= y1; ++j)
ans.push_back(matrix[x0][j]);
x0++;

// travel down side
for (int i = x0; i <= x1; ++i)
ans.push_back(matrix[i][y1]);
y1--;

if (x0 > x1) break;
// travel left side
for (int j = y1; j >= y0; --j)
ans.push_back(matrix[x1][j]);
x1--;

if (y0 > y1) break;
// travel up side
for (int i = x1; i >= x0; --i)
ans.push_back(matrix[i][y0]);
y0++;
}

return ans;
}``````

• like the game driven idea

• My idea is to shrink the border until reach the limit.

``````class Solution:
# @param matrix, a list of lists of integers
# @return a list of integers
def spiralOrder(self, matrix):
alist = []
while(True):
try:
# Top border
alist.extend(matrix.pop(0))
# Right border
for item in matrix:
alist.append(item.pop())
# Bottom border
alist.extend(matrix.pop()[::-1])
# Left border
for item in matrix[::-1]:
alist.append(item.pop(0))
# matrix.pop doesn't work if vide
except IndexError as indexerr:
break

if [] in alist:
alist.remove([])
return alist``````

• the idea of embedding direction into the algorithm is novel.
But acutually it sacrifies the readability of the code.
Considering the similar complexity of the code, I prefer the original one.

• Thanks for your clear code!

• so beautiful

• Why would you need to put the rowBegin<=rowEnd condition in front of the third loop? If the condition is not met shouldn't the while loop end immediately after the increment/decrement of these pointers?

• Think about a simple case like a 1X3 matrix.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.