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

Example:

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]

Solution

from typing import List

class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix:
return []

firstRow, firstCol = 0, 0
rows, cols = len(matrix), len(matrix[0])
result = []

while rows > 0 and cols > 0:
lastRow = firstRow + rows - 1
lastCol = firstCol + cols - 1

# Top left to right
for i in range(cols):
result.append(matrix[firstRow][firstCol + i])
# Right top to bottom
for i in range(1, rows):
result.append(matrix[firstRow + i][lastCol])
# Bottom right to left
for i in range(1, cols):
if firstRow != lastRow:
result.append(matrix[lastRow][lastCol - i])
# Left bottom to top
for i in range(1, rows - 1):
if firstCol != lastCol:
result.append(matrix[lastRow - i][firstCol])

# Next layer
firstRow += 1
firstCol += 1
rows -= 2
cols -= 2

return result


Test Cases

test = Solution()
[1,2,3],
[4,5,6],
[7,8,9]
])
[1,2,3,4],
[5,6,7,8],
[9,10,11,12]
])
[1,2,3],
[4,5,6],
[7,8,9],
[10,11,12]
])
[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16],
])