Print Spiral Matrix Python

Hello Everyone, today’s algorithm is the unintuitive “Print Spiral Matrix”. My friend got asked this question from Squarespace two years ago and I finally decided to tackle it. I failed, but shout out to the internet for eventually giving me the answer. Personally, I’d rate this a LeetCode medium-hard. It’s also a question on Pramp.

The concept:

Given a 2D array, NxN or NxM, print out its contents in spiral form. For example:

Screen Shot 2019-04-05 at 4.33.35 PM

Should return: [1, 2, 3, ‘a’, ‘b’, ‘c’, ‘d’, 12, 11, 10, 7, 4, 5, 6, 9, 8]

We are moving right, down, backwards, up while repeating over and over until complete. Each time, we decrement a row or a column.

*Note: The variable names in the video are different from the variable names in this blog post. It is the same algorithm however.

Here is the full code before I explain

Screen Shot 2019-04-07 at 2.27.44 PM

The Breakdown

Screen Shot 2019-04-05 at 6.23.01 PM

Here is the beginning of the algorithm. We define a function called printSpiral that holds a matrix/2D array. We define a list, result, that will later be returned. Next, are our variables. These will help us navigate through the matrix to grab the values we will need. All of these variables will either increment or decrement signifying that one entire column or row has been printed.

 

Screen Shot 2019-04-05 at 6.23.41 PM

The first step is moving to the right and grabbing the entire row. We make a while loop to continue until all rows and columns have been visited.  Our for loop starts at 0 on the first iteration and should continue until we’ve grabbed the end of the row. We make rightCol + 1 because we don’t want the range to stop before grabbing the last value in the row. We then append the current topRow (which will stay the same until the next for loop) with the incremented i. On first iteration, our values are matrix[0][0], then matrix[0][1], matrix[0][2], matrix[0][3], following the original matrix above. Once finished, we increment topRow by 1 as now we have completed an entire row.

 

Screen Shot 2019-04-05 at 6.23.57 PM

Now we are grabbing the end/right column. We are finished with the row above us, and the final element in the row above has already been grabbed. topRow has now been incremented to equal 1. i will follow suit. i will iterate from the current value of topRow, 1, to the end of the matrix’s column. btmRow + 1 is currently equal to 4 (following the example above), so we are grabbing matrix[1][3], matrix[2][3], matrix[3][3]

Next, we minus rightCol by 1 to signify that we have completed grabbing one column. If we are moving down again, our iteration will only grab up until the column before.

 

Screen Shot 2019-04-05 at 6.24.08 PM

Now moving backwards. As a reminder, Python ranges can include three arguments. Above, we are using the range(start, stop, step). When we have -1 as a step, this translates to Python that we are moving backwards. So, we are starting at 2 and iterating down up until -1. That means we are grabbing matrix[3][2], then matrix[3][1] and finally matrix[3][0]

We have finished grabbing the bottom row so we decrement btmRow by 1.

Screen Shot 2019-04-07 at 8.02.17 PM

Above, we move up grabbing the left column.We check to make sure the leftCol is less than or equal to the rightCol. If so, we continue our for loop. We are moving backwards once again. Starting from 2 and decrementing to 0. We grab matrix[2][0] then matrix[2][1]. Once again, following the example above. Finally, we increment leftCol to signify that  one more column is complete. We continue these steps (right, down, backwards, up) if the conditions are met and then return the final result.

 

Video Tutorial

 

Unit Tests

Definitely test your code. You should have a test.py file in a folder. Within that folder should be another folder that will hold the code above( mines is called spiralMatrix). The name of the file in it should be __init__.py. You will import the algorithm from this file into test.py as noted below.

Screen Shot 2019-04-10 at 11.15.07 AM.png

Mutated Version

Note: This version may be easier to understand but it is very expensive in time complexity.

Screen Shot 2019-04-08 at 12.55.55 PM

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s