# Spiral Matrix

This question was asked during my second round interview with Yahoo search team.

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

For example,
Given the following matrix:

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

You should return `[1,2,3,6,9,8,7,4,5]`.

My Solution

This is pretty straight forward O(mn) solution by traversing right, down, left, and up until it reaches the center. But careful with the duplication by restricting left and up traversal with the start/end indexes.

```def spiral_order(matrix):
if not matrix:
return []
res = []
rowStart, rowEnd = 0, len(matrix)
colStart, colEnd = 0, len(matrix[0])

# traverse until the center matrix
while rowStart < rowEnd and colStart < colEnd:
# traverse right
for i in range(colStart, colEnd):
res.append(matrix[rowStart][i])
rowStart += 1

# traverse down
for j in range(rowStart, rowEnd):
res.append(matrix[j][colEnd-1])
colEnd -= 1

# traverse left, careful on the duplication
if rowStart < rowEnd:
for k in range(colEnd-1, colStart-1, -1):
res.append(matrix[rowEnd-1][k])
rowEnd -= 1

# traverse up, careful on the duplication
if colStart < colEnd:
for l in range(rowEnd-1, rowStart-1, -1):
res.append(matrix[l][colStart])
colStart += 1

return res

```