Solving Spiral Matrix Problem

Recently I’ve been reviewing data structures and algorithms as part of my graduate studies. To further strengthen those skills, I’ve been practicing programming problems at least once a day over the past month and counting. The joy of solving programming problems is great, but sharing solutions is even better so everyone can benefit!

In my post here, I’ll go over the Spiral Matrix problem, specifically:

Analyzing it
Solving it using Swift

Problem Statement

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input: matrix = [[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]

Problem Analysis

Let’s break apart this problem step by step and understand our requirements:

We have an m x n matrix that’s given as an input
The expected output is a one-dimensional array
More specifically, the one-dimensional array contains values from the m x n matrix by traversing through in a spiral direction

Using example 2’s input and without thinking about code for a moment, how can we traverse through the matrix in a spiral direction?

Starting at 1 (row 1, column 1) we go right until we reach right-most column. So far, we covered 1, 2, 3, 4 ✔️
Starting from 4 (row 1, column 4), we go down until we reach the last row (row 3, column 4). So far, we covered 8 and 12 ✔️
Starting from 12 (row 3, column 4) we go left until we reach the left-most column (row 3, column 1). So far, we covered 11, 10, 9 ✔️
Starting from 9 (row 3, column 1) we go up until we reach the second top-most row (row 2, column 1). Why second top-most row? Because we already visited the first row, so we want to visit the top-most row that’s after the initial row. So far, we covered 5 ✔️

Now from 5, we’ll go right and collect 6 and 7 ✔️.

Example 2’s input is a small 3 x 4 matrix, but what if we had a 10 x 10 matrix - how would we traverse all of its values in a spiral direction?!

Notice in example 2’s input after step 4, we went right. Going right comes from step 1. In other words, for larger matrices we simply repeat steps 1 through 4 until all values are exhausted!

Now that we’ve understood how to solve this problem at a high-level, it’s time to plan out implementing our algorithm.

Solution

Track Indices & Elements

In order to traverse through the matrix in a spiral direction, we’ll need to have variables that keep track of index positions in the top row, bottom row, left column and right column.

We’ll also need to instantiate an array that stores elements while traversing through the given matrix.

Traversals

I'll setup 4 helper functions to handle right, down, left, and up traversals respectively.

Traverse right and increment topRow
Traverse down and decrement rightCol
Traverse left and decrement bottomRow
Traverse up and increment leftCol

Execute Traversals

Finally, I'll setup a while loop with a valid terminating condition that will ensure all elements are visited without repeating visits. I'll use topRow, bottomRow, leftCol and rightCol as the terminating conditions.

Final Solution

Putting it altogether, here’s our solution to this problem.

Results

Time Complexity: O(n^2)

LeetCode Performance:

Stellar runtime and memory performance 👏🏼

For any comments and questions on this post, follow up on Twitter.

Make sure to share this article. Appreciate you reading through my blog and until next time.