# 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) - 1            total_nums = len(matrix) * len(matrix)            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.

## More from Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt