Spiral Matrix — Day 26(Python)

Photo by Ludde Lorentz on Unsplash

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.

Tracing the path in 2D 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.

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store