Problem Statement:
“Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.”
Input:[
[ 1, 2, 3],
[ 4, 5, 6],
[ 7, 8, 9]
]
Output: [1,2,3,6,9,8,7,4,5]
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]
First, let’s look at the output format. Output is a plain one dimensional list. It’s a legitimate idea to start with an empty list that will be filled up eventually.
res = []
Now dive deeper into the matrix. No matter what is the dimension of the matrix, first row will go first. First check, if there is a first row. Then extend it to the res.
if matrix[0]:
res.extend(matrix[0]) #first row
matrix = matrix[1:] #As we are done with the first row, just get rid of it.
We will keep getting rid of the rows and columns that would already be added in our list ‘res’. As we going to follow a spiral direction in the matrix, after first row, it’s turn to work on the right most column. Right most column means the last element of each sub-list.
if matrix and matrix[0]:
for row in matrix:
res.append(row.pop()) #right side
Now it will follow the bottom row of the matrix. Bottom row means the last sub-list of the matrix.
if matrix:
res.extend(matrix.pop()[::-1])
At last, it’s time for first column. But as the pattern is following the spiral shape, first column will come from bottom to top.
if matrix and matrix[0]:
for row in matrix[::-1]:
res.append(row.pop(0))
This whole process should keep running in a loop till there are no more rows or columns. I am going to put it in a while loop and the name of the function is spiralOrder. Putting it all together:
def spiralOrder(matrix):
res = []
while matrix:
if matrix[0]:
res.extend(matrix[0]) #first row
matrix = matrix[1:]
if matrix and matrix[0]:
for row in matrix:
res.append(row.pop()) #right side
if matrix:
res.extend(matrix.pop()[::-1])
if matrix and matrix[0]:
for row in matrix[::-1]:
res.append(row.pop(0))
return res
