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.
Given a 2D array, NxN or NxM, print out its contents in spiral form. For example:
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
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.
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, then matrix, matrix, matrix, following the original matrix above. Once finished, we increment topRow by 1 as now we have completed an entire row.
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, matrix, matrix.
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.
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 i at 2 and iterating down up until -1. That means we are grabbing matrix, then matrix and finally matrix.
We have finished grabbing the bottom row so we decrement btmRow by 1.
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 then matrix. 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.
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.
Note: This version may be easier to understand but it is very expensive in time complexity.