# Spiral Matrix — Day 26(Python)

Today, we will be looking into one of Microsoft’s favorite interview questions in the technical coding challenge. Let us jump into the problem without wasting much time.

**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]

When we think of an array, we should imagine a data structure with contiguous memory allocation. When it comes to a 2D array, each cell is identified using row and column numbers.

To solve the given problem, we just need to learn how we can trace the path in our matrix. I have shown below, how we need to trace path, if we are given a 3x3 matrix.

A point to notice, once we traverse through a row or a column, we would never visit that row/column again. We need to keep track of rows/columns that we have already traversed. We can hold 4 variables that we keep track of traversed rows/columns. We need to start traversing the array from left to right, then top to bottom, later right to left and finally bottom to top.

The code will look like below.

`class SpiralOrderCreater:`

def spiralOrder(self, matrix):

nums = []

if(len(matrix) == 0):

return nums

else:

top = 0

bottom = len(matrix) - 1

left = 0

right = len(matrix[0]) - 1

total_nums = len(matrix) * len(matrix[0])

while(len(nums) < total_nums):

for i in range(left,right+1):

if(len(nums) < total_nums):

nums.append(matrix[top][i])

top += 1

for i in range(top, bottom+1):

if(len(nums) < total_nums):

nums.append(matrix[i][right])

right -= 1

for i in range(right, left-1, -1):

if(len(nums) < total_nums):

nums.append(matrix[bottom][i])

bottom -= 1

for i in range(bottom, top-1, -1):

if(len(nums) < total_nums):

nums.append(matrix[i][left])

left += 1

return(nums)

Complexity analysis

**Time Complexity**

We are looking at each element in our array once, and hence the time complexity is O(m*n).

**Space Complexity**

We are not using any extra space while finding the solution, except for the output array. We do not consider space used for output array, and hence space complexity is O(1).

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.