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`

.

1 2 3 4 5 |
//process first row while idx < start + columns { result.append(matrix[start][idx]) idx += 1 } |

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

.

1 2 3 4 5 6 |
//process right column idx = start + 1 while idx < start + rows { result.append(matrix[idx][start + columns - 1]) idx += 1 } |

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:

1 2 3 4 5 6 7 8 |
//process bottom row iff rows > 1 if rows > 1 { idx = start + columns - 2 while idx >= start { result.append(matrix[start + rows - 1][idx]) idx -= 1 } } |

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:

1 2 3 4 5 6 7 8 |
//process left column iff columns > 1 if columns > 1 { idx = start + rows - 2 while idx >= start + 1 { result.append(matrix[idx][start]) idx -= 1 } } |

Time Complexity: `O(MN)`

Space Complexity: No additional space needed.

Problem taken from Leetcode.

Solution hosted on Github.