Spiral Matrix Code Challenge in C++

Introduction

The problem isn't something that you see a lot, however knowing how to solve it can be a really impressive feat. Not too long ago I was asked this question during a live coding interview. I was told I could solve it in whatever language I chose. The particluar role I was interviewing for was one of C# so that is what I opted to solve the challenge in. I was able to solve it in the alotted time given and thought I would give it a shot in C++.

The Approach

In this section I want to cover the theory of what I chose to do and in the last section we will implement what I did in code. The approach I took uses four loops to traverse the matrix in a spiral order. The four loops correspond to the four directions (right, down, left, up) that the spiral will travel. The solution starts by traversing the top row going from left to right, then the right column from top to bottom, then bottom row from right to left and of course finally finishing off the left column from bottom to top. We also use four variables, which are of course just the first letters from each direction(u, d, l, r) to keep track of teh bounds of the matrix. These variables represent the top row(u), bottom row(d), left column(l) and right column(r) of the matrix. We update these variables as we traverse the matrix to ensure that it doesn't visit the same cell more than once.

Let's write the code and run it to see what we get.

Optimizing Our Solution

One optimization we can make is to use a single loop instead of four separate ones to traverse the matrix in a spiral order. This will reduce the overall complexity of the solution making it go from O(n^2) to O(n). The code solution for better optimization is as follows:

Conclusion

I hope that you enjoyed learning more about the spiral matrix problem and how you can solve it using C++. Now if you run this program you will see that it doesn't quite print them in the way of a spiral but you can see that the arrays are indeed in the correct order as though the are sprialing. I leave it to you as a challenge to try to add that feature.