Coding Challenges — Spiral Matrix
Continuing with the theme of learning data structures and algorithms, this is my attempt at explaining the most-difficult problem that I have yet to face: the Spiral Matrix Problem.
Problem Statement
Given an integer, n, write a function that creates a spiral matrix that has dimensions of n x n.
This is a bit tricky to conceptualize without an example, so this is what our desired result will look like.
function matrix(n){
//our code
}matrix(3)[[1, 2, 3],[8, 9, 4],[7, 6, 5]]
So, as you can see, we want to create a function that iterates through this matrix, starting from 1 and ending at the product of n². For this example, I will be using an initial integer of 3 for n, just to keep it a bit simpler.
Step 1: How to Picture the Solution
The first thing that we need to do to understand this problem is to find a certain pattern. Here, the first thing that we should examine is the data structure that we will be using to create the matrix; in this case, an array of arrays.
Moving on from there, we can see that the number of arrays within the initial array is equal to the value of n, which is, in this case, 3. So, our first step is to initialize that initial array, which we will call results, and populate it with n number of arrays. This can be accomplished with a simple for loop.
function matrix(n) {
const results = []; for(let i = 0; i < n; i++){
results.push([]);
}}console.log(results) => [[],[],[]];
So, with this iteration, starting from 0, we push a new, empty array into the master array, results. Cool!
Step 2: Setting Our Initial Values and Trackers
Our approach here will be to iterate through the matrix by thinking of it as a grid. We will set initial values of the start column and start row, the end column and end row, and the count variable, which will be the actual integers that populate the arrays.
Note: we want to start the values that will be placed inside the subarrays at 1. Our initial set up will look like this.
function matrix(n) {
const results = [];for(let i = 0; i < n; i++){
results.push([]);
} let startRow = 0;
let endRow = n - 1;
let startCol = 0;
let endCol = n - 1;
let count = 1;}
Due to the fact that we are working with indices, our values for the start are set to 0, and the end are set to the value of n — 1. It is important to understand that these values will all be changing throughout our iterations, i.e. the start and end points will be adjusted according to which row or column we are populating.
Step 3: Setting Up Our While (Master) Loop
In total, we will be using 5 for loops and 1 while loop to complete this exercise. The first for loop was already defined, and pushes the subarrays into the results array. Now, we want a while loop that will execute until certain conditions are met. In this case, we have two conditions.
- We will iterate while startRow is less than or equal to endRow
AND
2. While startCol is less than or equal to endCol
function matrix(n) {
const results = [];for(let i = 0; i < n; i++){
results.push([]);
}let startRow = 0;
let endRow = n - 1;
let startCol = 0;
let endCol = n - 1;
let count = 1; while(startRow <= endRow && startCol <= endRow){
//do something
}}
Step 4: Populating the Top Row
The first thing we want to do is fill the top row with values. To do this, we will need to utilize both the row and column indices.
Although we are populating the top row, we actually want to control the iteration through the columns. We are moving from left to right, so the startCol will be our starting point, or i. Our endpoint will be endCol, which is at index 2. We will iterate until startCol equals endCol.
Now, we want to think about where we want to place these values, i.e. in which subarray and at which indices to place them.
Due to the fact that we are placing values in the startRow subarray, this will be how we identify the first subarray in results. The value, i, will represent each index within the subarray.
Finally, we will set the value equal to count, which will be incremented each time, until it is equal to the product of n².
Once we are finished with this iteration, we want to move to the second row, because our top row will be populated. So, we increment the value of startRow, which will then equal 1.
function matrix(n) {
const results = [];for(let i = 0; i < n; i++){
results.push([]);
}let startRow = 0;
let endRow = n - 1;
let startCol = 0;
let endCol = n - 1;
let count = 1; while(startRow <= endRow && startCol <= endCol){
//top row
for(let i = startCol; i <= endCol; i++){
results[startRow][i] = count;
count++
}
startRow++ }}
Step 5: Right Column
Now, our matrix should look like this. The x’s denote an empty space.
console.log(results) => [
[1,2,3],
[x,x,x],
[x,x,x]
];
Variable Changescount => 4;
startRow => 1;
So, we want to populate the right column, starting at index 2 of the second subarray at index 1. Just like we used columns to populate the top row, we will now use the rows to populate the right column. We will then decrement the endCol variable to move left in our matrix.
function matrix(n) {
const results = [];for(let i = 0; i < n; i++){
results.push([]);
}let startRow = 0;
let endRow = n - 1;
let startCol = 0;
let endCol = n - 1;
let count = 1;while(startRow <= endRow && startCol <= endCol){
//top row
for(let i = startCol; i <= endCol; i++){
results[startRow][i] = count;
count++
}
startRow++ //right column
for(let i = startRow; i <= endRow; i++) {
results[i][endCol]= count;
count++
}
endCol--;}}
Now, we have this.
console.log(results) => [
[1,2,3],
[x,x,4],
[x,x,5]
];
Variable Changescount => 6;
startRow => 1;
endCol => 1;
Step 6: Bottom Row
Above, we decremented the end column by 1. We are now starting with the value that will be located at endRow[1] and endCol, which is now 1.
We will again use the column as a guide when we iterate through the bottom row, and iterate until the end column is equal to the start col, a total of two iterations. It is important to note that we will decrement i, because we are moving from right to left.
function matrix(n) {
const results = [];for(let i = 0; i < n; i++){
results.push([]);
}let startRow = 0;
let endRow = n - 1;
let startCol = 0;
let endCol = n - 1;
let count = 1;while(startRow <= endRow && startCol <= endCol){
//top row
for(let i = startCol; i <= endCol; i++){
results[startRow][i] = count;
count++
}
startRow++//right column
for(let i = startRow; i <= endRow; i++) {
results[i][endCol]= count;
count++
}
endCol--; //bottom row
for(let i = endCol; i >= startCol; i--){
results[endRow][i] = count;
count++
}
endRow--;}}console.log(results) => [
[1,2,3],
[x,x,4],
[7,6,5]
];
Variable Changescount => 8;
startRow => 1;
endCol => 1;
endRow => 1;
Step 7: Left Row
Almost there! This will be our last for loop. Now, we want to move up startCol, using startRow and endRow to guide us. Once again, we will decrement i, because we are moving from endRow to startRow.
function matrix(n) {
const results = [];for(let i = 0; i < n; i++){
results.push([]);
}let startRow = 0;
let endRow = n - 1;
let startCol = 0;
let endCol = n - 1;
let count = 1;while(startRow <= endRow && startCol <= endCol){
//top row
for(let i = startCol; i <= endCol; i++){
results[startRow][i] = count;
count++;
}
startRow++//right column
for(let i = startRow; i <= endRow; i++) {
results[i][endCol]= count;
count++;
}
endCol--;//bottom row
for(let i = endCol; i >= startCol; i--){
results[endRow][i] = count;
count++;
}
endRow--; //left column
for(let i = endRow; i >= startRow; i--){
results[i][startCol] = count;
count++;
}
startCol++;}}console.log(results) => [
[1,2,3],
[8,x,4],
[7,6,5]
];
Variable Changescount => 9;
startRow => 1;
endCol => 1;
endRow => 1;
startCol => 1;
Note: each variable that was initially defined has now been changed in some way. This is the key to solving this problem: keeping track of the changing values of the rows and columns, as well as the count.
Step 8: The Final Value
So, after we meet the conditions of the last for loop, we jump back to the top of the while loop to check our conditions.
while(startRow <= endRow && startCol <= endCol); Variable Valuescount = 9;
startRow => 1;
endRow = 1;
startCol => 1;
endCol => 1;
Basically, we will now go through the while loop once more, after which one of our conditions breaks (*hint hint*).
We will pass through our first for loop. In the second row results[startRow] at the index of 1 (startCol), we place the current value of count, which is now 9. startRow is incremented by 1.
End Values of VariablesstartRow => 2;
endRow = 0;
startCol => 2;
endCol => 0;
count = 10;
Now, our conditionals for the while loop are met, because both the starting values for column and row exceed the end values. Phew!
Final Result
console.log(results) => [
[1,2,3],
[8,9,4],
[7,6,5]
];count => 2;
startRow => 2;
startCol => 2;
endRow => 0;
endCol => 0;
So, we have what we want! All that we have to do is return results, and we are on the gravy train with biscuit wheels. Here is the final function.
function matrix(n) {const results = [];for(let i = 0; i < n; i++){results.push([]);}let startRow = 0;let endRow = n - 1;let startCol = 0;let endCol = n - 1;let count = 1;while(startRow <= endRow && startCol <= endCol){//top rowfor(let i = startCol; i <= endCol; i++){results[startRow][i] = count;count++;}startRow++//right columnfor(let i = startRow; i <= endRow; i++) {results[i][endCol]= count;count++;}endCol--;//bottom rowfor(let i = endCol; i >= startCol; i--){results[endRow][i] = count;count++;}endRow--;//left columnfor(let i = endRow; i >= startRow; i--){results[i][startCol] = count;count++;}startCol++;}return results}
I know that your mind is probably boggled by now, because mine is as well. This problem took me a long time to work through, because it has a lot of moving pieces. My recommendation is to open a console in your browser, paste the final version of the function, add a debugger, and step through EVERY SINGLE iteration until it makes sense. As always, Happy Coding!
