Unfurling a Matrix in JS

In my first technical interview, I was given a few questions to check basic comprehension of JavaScript. There were a few classic problems, but the one that sticks out to me was the algorithm
test, which was one of those things that seemed completely difficult in the abstract but, like many things, makes perfect sense with a little goading. I was fortunate to have a very generous interviewer who prodded in the right ways.

The problem I was given was to unroll a snail matrix (array of arrays) into a single matrix—that is, given a matrix where numbers are presented sequentially in a spiral pattern, unfurl the matrix, preserving the correct order of numbers. A caveat was that the matrix function could be destructive to the original matrix (this helps a lot!). To start, let's look at a test case that we'll follow as we implement this.

let myMatrix = [[1, 2, 3, 4],
                [12,13,14,5],
                [11,16,15,6],
                [10,9, 8, 7]];

With ES2019, there is a very simple one line coding solution, which simply involves flattening the array and sorting it. Array.prototype.flat() takes an argument of depth, which defaults to one, and because this is an array of depth one, we don’t need an argument. Our function would look like this.

myMatrix.flat().sort((a, b) => a - b)

It's worth checking out (Mozilla's documentation)[https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/flat] for this, which shows us that the flat() portion of this function is akin to arr.reduce((acc, val) => acc.concat(val), []);

I did not know about flat() when I did this technical interview in the final weeks of my bootcamp, and while this is a great solution, I believe this interviewer wanted to see a grasp of fundament concepts.

To begin broaching this problem, I kept in mind the fact that we could be destructive to the original matrix, which is a huge help, so I decided to begin the function by generating a new array. To unfurl the matrix, we would navigate around the matrix in a spiral pattern, popping and shifting values from the matrix into this new array.

The first step is pretty easy. The first row of the matrix—that is, the first subarray—is where we begin. This subarray is in order, so we can just pop this whole array into the new array. Destructuring allows for a very clean syntax, so we can restructure the matrix, use shift() to remove the entire first subarray, and then push this to our new array. To begin, our function looks like:

const newArr = []
newArr.push(...map.shift())

Let's check in our matrix and newArr:

myMatrix = [[12,13,14,5],
            [11,16,15,6],
            [10,9,8,7]];
newArr = [1, 2, 3, 4]

The second step is a bit trickier, as we have to move capture the last value in every subarray—the rightmost column of the matrix if you will. We know that we can use pop() to remove the last value in any matrix, so this will be a helpful tool. One way of capturing these values could be a for loop, which might look like:

for(let i = 0; i < matrix.length; i++){
    let lastVal = matrix[i].pop()
    newArr.push(lastVal)
}

But once again, there is a cleaner way of doing this using destructing and map, as we are capturing the same value in every subarray. We can simply write: newArr.push(...matrix.map(arr => arr.pop())). Again, let's look at that matrix.

myMatrix = [[12,13,14],
            [11,16,15],
            [10,9,8]];
newArr = [1, 2, 3, 4, 5, 6, 7]

Figuring out these first two steps is critical, as it provides the basis for most of the work we need to do on this matrix. In that last row, we need to capture the values [10, 9, 8], and we can use the same method we used to capture that first row, as long as we call reverse() on the entire subarray.

We can implement that same reverse logic to traverse the first column of the matrix as well. Much like we did on the right edge, we can just call map and and shift() (rather than pop(), since we want the first values in every subarray), but because those values are organized bottom to top rather than top to bottom, we once again need a reverse. Here, our functions look like:

// bottom row
newArr.push(...matrix().pop().reverse())
//left edge
newArr.push(...matrix.map(arr => arr.shift()).reverse())

Following these steps, our matrix and array look like:

myMatrix = [[13,14],
            [16,15]];
newArr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

This is good progress, but what about those remaining values? We could try and implement some new logic to keep capturing values, or we could recognize the strength of the code that we already. I think here, there are two options: the first would be to throw the code inside some kind of while loop, that keeps running while matrix.length > 0. Or we could just make the function recursive. I chose the latter option, which requires simply calling the function on itself, as well as adding in a break statement, in this case if (matrix.length === 0). Finally, we need to return the newArr.

In total, the function looks like this.

function unroll(matrix) {
  const newArr = []
  if (matrix.length === 0) return ;
  // first row
  newArr.push(...matrix.shift())
  // right edge
  newArr.push(...matrix.map(arr => arr.pop()))
  //bottom in reverse
  newArr.push(...matrix.pop().reverse())
  // left edge
  newArr.push(...matrix.map(arr => arr.shift()).reverse())
  unroll(matrix)
  return ...newArr
}

This is only eight lines of code, but it turned out to be a good technical test because it really checks basic comprehension: do you know how to perform basic operations on an array? Do you know ES6? Do you understand recursion? All essential skills. But in the wild, I think I would just flatten and sort the array.