Toy Problem: Spiral Traversal

Hack Reactor

Hi guys, I decided today to start writing toy problem solutions that I have encountered and I did not know how to solve most of them, but I found out when I try to explain the issue to someone I can resolve it.

Let’s Get started🎉

.This is yet another way to use recursion and a fun one at that. This one definitely had me stumped for a while and I am here to help walk through one of many ways that you might solve this problem. Anyway, let's get right into it. The problem will probably be similarly presented as such.

I’m using vs code, it's a very good software that has a beautiful interface and many features.
my vs code theme is: “hyper Dracula”

Write a function that accepts a 2-dimensional array (that is, an array containing many same-length arrays), and prints out every value found, but in a spiral from the upper left into the center.
Please write some form of specs, tests, or assertions for your code, and check as many edge cases as you can think of.

example:

spiralTraversal([
[1,2,3],
[4,5,6],
[7,8,9]
]);

returns [1, 2, 3, 6, 9, 8, 7, 4, 5]

I believe that there are multiple ways to solve this toy problem but here is one way that I found.

  1. let spiralTraversal = function (matrix,result = []) {
    //we need too create a variable to store our element inside it then we //will return it in the end.
    return result

by the way, we can create the result array this way to store our element or we can simply create it outside of the function so we can make it a global variable.

2. the first thing you might notice is that the first three numbers from the example output are just the first element from the first array. There are many ways that you may approach this, but here is one way.

let spiralTraversal = function (matrix,result = []) {
// if the length of the matrix ==0 we will return the result

if (matrix.length == 0) {

return result;
}
return result

There! We pull out all the elements from the first array using shift.
I highly recommend you to use a debugger so you can see how things are being read by the interpreter so you can understand even more.

That’s one less array we have to worry about. So we have our upper left to upper right spiral completed. Just 3 more left to go!
So next we need to pull out the whole right side of our matrix.
How can we do that? With a simple array method, .pop()
Since we aren’t going through one whole array we can just use a simple forEach here.

let spiralTraversal = function (matrix,result = []) {
// if the length of the matrix ==0 we will return the result

if (matrix.length == 0) {

return result;
}

// we need to push the elements inside the first element of the array //then delete this element

while (matrix[0].length) {

result.push(matrix[0].shift());

}

return result

So right now we have completed the first two rounds. So you might have guessed by now that the next two are very similar to the first two. And if you guessed that, then you are absolutely right! We just need to do what we did the first time but in reverse!

let spiralTraversal = function (matrix,result = []) {
if (matrix.length == 0) {
return result;
}
while (matrix[0].length) {
result.push(matrix[0].shift());
}
//let’s go from top right to bottom right
matrix.forEach((row) => {
result.push(row.pop());
});
return result

Now we need to go from the bottom right to bottom left

let spiralTraversal = function (matrix,result = []) {
if (matrix.length == 0) {
return result;
}
while (matrix[0].length) {
result.push(matrix[0].shift());
}
matrix.forEach((row) => {
result.push(row.pop());
});
return result

we need reverse again so we can retraverse on the next iteration by simply using the method reverse of the arrays

matrix.reverse();

then filter out any empty arrays

matrix = matrix.filter((element) => element.length);

Now, all we have left to do is our base case and our recursive case. And we can simply do that by adding and modifying a few lines. And finally, we will end with our function looking something like this.

var spiralTraversal = function (matrix, result = []) {
// TODO: Implement me!
// if the length of the matrix ==0 we will return the result
if (matrix.length == 0) {
return result;
}
// we need to push the elements inside the first element of the array //then delete this element
while (matrix[0].length) {
result.push(matrix[0].shift());
}
//top right to bottom right
matrix.forEach((row) => {
result.push(row.pop());
});
//bottom right to bottom left.
while (matrix[matrix.length — 1].length) {
result.push(matrix[matrix.length — 1].pop());
}
//reverse again so we can retraverse on the next iteration.
matrix.reverse();
//filter out any empty arrays
matrix = matrix.filter((element) => element.length);
//recursive case.
result = spiralTraversal(matrix, result);
//return spiral and filter any undefined elements.
return result.filter((element) => element);
};

Now I have provided some pseudocode so that you can tell how this function works its magic! Now if we run our function it should output this!

🙌==>>>>[1, 2, 3, 6, 9, 8, 7, 4, 5]

I hope that I could have delivered clear information, and if you get the concept, please share it with your friends, and if you have any questions write it below.

If you want master something teach it.