Toy Problem Time: Spiral Traversal

Hey there friends and fellow developers! Today I am back again to tell all of you about yet another fun toy problem, spiral traversal. 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, lets get right into it. The problem will probably be similarly presented as such.

Write a function called traverseSpiral that accepts a 2-d array (that is, an
array containing many same-length arrays), and returns an array with every value
found, but in a spiral from the upper left to the center.

Where an input 'spiral' might look like this.

[
  [1,  2,  3,  4],
  [5,  6,  7,  8],
  [9, 10, 11, 12],
]

And the output would look like this.

[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Now this may be a little overwhelming at first, especially when you think about how big a spiral can be, but it is really not half as bad as you might initially think. Let's break it down.

const travereSpiral = (matrix, spiral = []) => {
  // TODO: Your code here!

  return spiral
};

NOTE: I have started us off with an empty array as a default parameter.

The first thing you might notice is that the first four 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.

const traverseSpiral = (matrix, spiral = []) => {
  // TODO: Your code here!
  while(matrix[0].length){
    spiral.push(matrix[0].shift());
  }

  return spiral;
};

There! We pull out all the elements from the first array using shift. Now if we were to run our function with our example input this is how our input and output should look at this point. And from this point on I will be showing the input and output to give you a visual of how it looks after every piece we break down.

//input
[
  [],
  [5,  6,  7,  8],
  [9, 10, 11, 12],
]

//output
[1,  2,  3,  4]

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.

const traverseSpiral = (matrix, spiral = []) => {
  // TODO: Your code here!
  while(matrix[0].length){
    spiral.push(matrix[0].shift());
  }

  matrix.forEach(row =>{
    spiral.push(row.pop());
  });

  return spiral;
};

//input
[
  [],
  [5,  6,  7],
  [9, 10, 11],
]

//output
[1,  2,  3,  4, 8, 12]

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!

const traverseSpiral = (matrix, spiral = []) => {
  // TODO: Your code here!
  while(matrix[0].length){
    spiral.push(matrix[0].shift());
  }

  matrix.forEach(row =>{
    spiral.push(row.pop());
  });

  while(matrix[matrix.length - 1].length){
    spiral.push(matrix[matrix.length - 1].pop());
  }

  matrix.reverse().forEach(row =>{
    spiral.push(row.shift());
  });

  matrix.reverse();

  return spiral;
};

Now after all that our input and output should look something like this.

//input
[
  [],
  [6,  7],
  [],
]

//output
[1,  2,  3,  4, 8, 12, 11, 10, 9, 5]

There we have our first spiral! How can we do it again you might ask, well with our friend recursion! However, before we get to using recursion, lets first filter out those pesky empty array elements in our matrix array so that we do not have any bugs in the future.

const traverseSpiral = (matrix, spiral = []) => {
  // TODO: Your code here!
  while(matrix[0].length){
    spiral.push(matrix[0].shift());
  }

  matrix.forEach(row =>{
    spiral.push(row.pop());
  });

  while(matrix[matrix.length - 1].length){
    spiral.push(matrix[matrix.length - 1].pop());
  }

  matrix.reverse().forEach(row =>{
    spiral.push(row.shift());
  });

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

  return spiral
};

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.

const spiralTraversal = (matrix, spiral = []) => {
  // TODO: Your code here!
  //base case
  if(!matrix.length){
    return spiral;
  }

  //top left to top right
  while(matrix[0].length){
    spiral.push(matrix[0].shift());
  }

  //top right to bottom right
  matrix.forEach(row =>{
    spiral.push(row.pop());
  });

  //bottom right to bottom left
  while(matrix[matrix.length - 1].length){
    spiral.push(matrix[matrix.length - 1].pop());
  }

  //bottom left to top left
  matrix.reverse().forEach(row =>{
    spiral.push(row.shift());
  });

  //reverse again so we can retraverse on the next iteration
  matrix.reverse();

  //filter out any empty arrays
  matrix = matrix.filter(a => a.length);

  //recursive case
  spiral = spiralTraversal(matrix, spiral);

  //return spiral and filter any undefined elements
  return spiral.filter(e => e);
};

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, 4, 8, 12, 11, 10, 9, 5, 6, 7]

See that wasn't so hard?

Thanks so much for reading! If you haven't read my last post in my 'Toy Problem Time' series, click here! I hope to see you in my next post. As always, happy coding hackers!