Data Structure and Algorithm Common Interview question the Matrix Spiral.
Please check my past blogs series for more exercise.
The challenge we are discussing here is probably one of the toughest to understand and even tougher to explain, and you will probably see why as soon as I explain it.
The question
Write a function that accepts an integer N and returns an NxN spiral matrix.
Examples
matrix(2)[[1, 2],
[4, 3]]matrix(3)[[1, 2, 3], [8, 9, 4], [7, 6, 5]] matrix(4)[[1, 2, 3, 4],[12, 13, 14, 5],[11, 16, 15, 6],
[10, 9, 8, 7]]
It's not really clear the above explanation and example, so let’s first try to visualize what the solution should look like. We are getting and N number in our function, and we are required to return and NxN Spiral Matrix.
We need to create an array that takes some subarrays and returns the number inside the subarray in a way to create something like the below spiral. So our counter should follow the spiral partner.
For example, we are going to use N = 3. If you look at the below shape and then at the output of the example considering that N = 3 you will have a clear picture of the challenge requirement now.
The Solution
To solve this challenge, we require multiple steps. I will draw step by step in which point of the code and solution we are for a better understanding.
We need to visualise the solution In a Matrix and assgin variable to start row and end row, and same for the column we need to assign variable to start column and end column.
In the below example, you have the Matrix of the solution, plus I added the numeric value to each variable directly on the picture so you can follow step by step.
- Create a result variable and assgin an empty array
- Push in the result array a number X of the nested array equal to the N value input.
Now we should start to solve our challenge with a result array that looks like this:
[[ ],[ ],[ ]]3. create 5 variable, one of the counter starting at 1 a startCoumn starting at 0 and a startRow starting at 0. To find the endColum and the endRow we need to do N -1. In this case, our input example is 3, so we have [3–1 = 2].”
4. Now we need a while loop that keeps running until our start column is less or equal to the end column && start row is less or equal to the end row.
Now we need to start put some value in our nested arrays and increment the value of the variable created.
5. First we need to take care of our top row in the solution;
We need to write multiple for loop, and the first one will take care of this top row.
We are going to iterate from the start column to the end column and increment the start column inside our loop. And in the meantime push, the counter value in our first nested array.
This loop will fill up our first row and in the end increment the row variable by 1.
At this point, our array result looks like this:
We solved the top row, and our start row now is incremented by one, and our counter is now equal to 3.
6.Now we need to take care of the right-hand side column.
Our second loop will start from start row, which is equal to 1 now and loop to the end row.
Now we are targeting the last two nested array, and we want to push the value at the last index of each nested array. result[i] will grab the array at the index 1 which is the value of our starRow, and result[i][endColum] is going to push the result of the counter in the last index equal to 2 of our nested arrays. In the end, we need to decrement the endColumn variable by 1.
Now our result array looks like this.
As you can see, we solved the right column, and our end column now is decremented by one.
7.Now we need to solve the bottom row.
For this for loop, we are going to iterate from our end column which starts at 1 through the start column equal to 0.
Results [endRow] will target the last nested array, and results[endRow][i] will push the result into the middle index and decreased the result until to fill up all the bottom row. In the end, we need to decrease our end row by 1
Now our result array looks like this:
You can see that the bottom row now is completed and we moved up to one our end row to target the middle part of our matrix diagram.
8. In this for loop we need to take care fo the left side column;
This last for loop will iterate from the end Row which is now equal to 1 through the start row in this case equal to one so in this case we are going to make just one single loop. In the end, we need to increment the start column by 1.
results[i] should give us the middle nested array at index 1 and results[i][startColumn] will place the counter result in index 0 of the nested array.
Now our result looks like this:
Now our while loop will run one more time and will fill up the missing middle value, the only for loop that will runt this time is the first one and after that will exti our while loop, and we return the result array.
The full code:
I hope you enjoyed my matrix challenge, and you could follow the logic of the solution. If you have an any better solution, please leave feedback in the comment.
