## 54. Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

``````Input:

[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]

Output:
[1,2,3,6,9,8,7,4,5]
``````

Example 2:

``````Input:

[
[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]
``````

Thoughts:

1. having four markers: rowBegin, rowEnd, colBegin, colEnd,
2. go right -> incre rowBegin; go down -> decre colEnd; go left -> check(rowBegin <= rowEnd), decre rowEnd; go up ->check(colBegin <= colEnd), incre colBegin

Code Java

``````class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new LinkedList<Integer>();
if(matrix.length == 0) return res;

int rowBegin = 0, rowEnd = matrix.length - 1;
int colBegin = 0, colEnd = matrix[0].length - 1;
while(rowBegin <= rowEnd && colBegin <= colEnd){
// go right
for(int j = colBegin; j <= colEnd; j++){
res.add(matrix[rowBegin][j]);
}
rowBegin++;

// go down
for (int i = rowBegin;  i <= rowEnd; i++){
res.add(matrix[i][colEnd]);
}
colEnd--;

// go left
if(rowBegin <= rowEnd){
for(int j = colEnd; j >= colBegin; j --){
res.add(matrix[rowEnd][j]);
}
}
rowEnd--;

// go up
if(colBegin <= colEnd){
for(int i = rowEnd; i >= rowBegin; i--){
res.add(matrix[i][colBegin]);
}
}
colBegin++;
}

return res;
}
}
``````
``````class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
res = []
if not matrix: return res

rowS, colS, rowE, colE = 0, 0, len(matrix) - 1, len(matrix[0]) -1

while rowS <= rowE and colS <= colE:
# right
for j in range(colS, colE + 1):
res.append(matrix[rowS][j])
rowS+= 1

# down
for i in range(rowS, rowE + 1):
res.append(matrix[i][colE])
colE-= 1

# left
if rowS <= rowE:
for j in range(colE,colS - 1,-1):
res.append(matrix[rowE][j])
rowE -= 1

# up
if colS <= colE:
for i in range(rowE, rowS - 1, -1):
res.append(matrix[i][colS])
colS+= 1

return res
``````

from qwl5004's post