Leetcode – 54. Spiral Matrix

Reading Time: 2 minutes

The first idea that popped in my head after reading this problem is to start at index [0,0] and move right, walk down all the columns, turn right, walk down all the rows, move right, walk down all the columns in decreasing order, move right, walk up all the rows in decreasing order. At this point, how do we keep track that we have already visited [0,0] and this time we have to turn right and walk down the row with index 1?

I came up with a sample matrix on paper and started tracing out the order in which the elements need to be processed.

For example, given the following matrix:

You will see that once the outer red path has been completely visited, we are left with a sub array starting at index [1,1]. Once the blue path has been visited, we are left with a sub array starting at index [2,2] and so on, and at every iteration the number of rows and columns reduces by 2.

Since at the end of every iteration, we are left with a sub array to solve, hence, all I need now is to write a function taking the start coordinate and number of rows and columns to process, will go through and process the perimeter of the sub array.

The first for loop will be responsible for printing the top row from index start..<start+columns.

The second loop will be responsible for printing the right column from index start+1..<start+rows.

At this point, we should be asking ourselves whether we need to process the bottom row? Yes, iff the number of rows to be processed is greater than one. Therefore, the code to process the bottom row which will process the matrix from start+columns-2...start, will look like:

Now we have to ask ourselves whether the left column needs to be processed? Yes, iff the number of columns is greater than one. Therefore, the code to process the left column which will process the matrix from start+rows-2...start+1 will look like:

Time Complexity: O(MN)

Space Complexity: No additional space needed.

Problem taken from Leetcode.

Solution hosted on Github.

Mohit AthwaniLeetcode – 54. Spiral Matrix

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.