Spiral Traversal
Published: 2020-01-20 04:26:12

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/fuixzla6ypzzqquexcd3.jpg)

Imagine you have a matrix, and you want to return it entry by entry, but instead of by column, or by row, you want to return its elements as if you were iterating through them as a spiral. You would start at 0,0 and then work your way around the entirety of its outer edges, and then one step in. As a coding dilemma, this is an intriguing question. It's really only asking for you to iterate, and yet converting the geometric framing of this question into code can become quickly confusing. This is one of those problems that remind me how important it can be in code to follow the same principles I do in writing. Sometimes, the best first step isn't thinking through everything, it's to just start writing. Get something on paper, or in this case screen, and work from there.

First, we know we're going to be iterating over every element in this matrix during our function, so we might as well start with that. 

``` 
let result = [];
for (let j = 0; j < matrix[0].length; j++){
        result.push(matrix[0][j]);
      }
```
if our matrix is composed of nested arrays, perhaps like this : 
[
[0,1,2],
[3,4,5],
[6,7,8]
]
then this line of code would get us 
[0,1,2]
Well, this is good! Not only have we managed to iterate, which is something we know we have to do, we've also managed to write an iteration that grabs exactly the first three elements we wanted to.
Of course, this isn't the full solution. We need the next line, but simply repeating what we've written on the next internal array won't work. That would give us :0,1,2,3,4,5. But we need the 5 and the 8 next, so this is, of course, no good. We're doing something so similar to what we did above though, we're just moving 'down' instead of 'right.' We can actually use some code incredibly similar to the code above, but instead of iterating over the nested array, we'll iterate over the outer array and keep our second index, the internal index, constant. like so
```
for (let i = 0; i < matrix.length; i++) {
        result.push(matrix[i][matrix[0].length - 1]);
      }
```
Well, this is great. Almost. combining our two sets of code so far would give us 0,1,2,2,5,8. We're running down instead of right, just like we intended, but we're catching the 2 a second time on our way down.
I can think of two ways of preventing this. We could catch the 2 again, but add an if statement to check if we've ever used this set of coordinates before. Of course, then we'd have to store every set of coordinates we've ever used, and iterate over that on every element, taking what could be a linear time complexity operation and increasing it to quadratic. That doesn't seem great, plus that solution seems to be missing the crux of our problem. Obviously, we don't want the computer to even START to check an element it's already grabbed before. So why don't we just increase our starting point. instead of i = 0, we can just use i = 1. This does solve the problem but feels a bit like we're hard coding. as we move along, that 1, will have to be 2 if we start in on a deeper layer. the next layer it would iterate to 3. since a single constant wouldn't really do, let's use a variable instead. I'm going to name mine 'space', to represent the spacing in as we go along. Please feel free to use a better name for yours.

Now the next two directions are really similar to the last two and can be pretty easily written by just doing them in reverse, and of course including our space variable. But once we've covered the outer permitter you'll see we have another 'spacing' problem. When we apply the upwards iteration we end up grabbing 0 all over again! This is still a spacing problem, and that space variable being set at one does seem like it could help us here, so on this last line, let's add that into our stopping condition on our loop. instead of stopping at 0, we'll stop it at 1.

Well, if this was called circle traversal we would be done. But unfortunately, we need to move into our next spiral. I think we can instinctually tell that writing any more for loops from scratch to cover this movement would be a hardcoded solution. We've encapsulated the core iterating behavior we want already, we just need to move it into a container, and use a for loop to encapsulate the movement inwards on each iteration. Like below. I hope this has been an interesting and helpful read on one approach to solving coding problems. Don't be afraid to write code! every wrong step is just one step closer to the right step. :) 

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/s6p2tzz82tqw5lq5nbyu.png)

```const spiralTraversal = (matrix) => {
  // TODO: Your code here!
  let space = 0;
  const result = [];
  //fewest lines of code to solve this?
  let goal = matrix.length * matrix[0].length;
  
  while(result.length < matrix.length * matrix[0].length){
    if (result.length < goal){
      for (let j = space; j < matrix[0].length - space; j++){
        result.push(matrix[space][j]);
      }
    }
    if (result.length < goal){
      for (let i = space + 1; i < matrix.length - space; i++) {
        result.push(matrix[i][matrix[0].length - 1 - space]);
      }
    }
    if (result.length < goal) {
      for (let j = matrix[0].length - 2 - space; j >= space; j--) {
        result.push(matrix[matrix.length - 1 - space][j]);
      }
    }
    if (result.length < goal) {
      for (let i = matrix.length - 2 - space; i >= 1 + space; i--) {
        result.push(matrix[i][space]);
      }
    }
    space++;
  }
  return result;
};```