Algorithm practice: The matrix unroll

23 Sep 2019 - John

I ‘ve been working on my algorithm skills and recently came upon an excercise that while simple, proved to be both amusing and deceptively challenging. We are given an array comprised of n arrays. Each array, in turn, is also n in length:

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

Our job is to take the matrix and print its contents starting from the fisrt number and then continue to do so in a spiral, clockwise fashion until there is nothing else to print.
With the matrix we currently have, the result should be 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10

Credit: pxfuel

How to approach?

The best way to approach this problem is to recognize a series of patterns:

First we have to get the horizontal row in its entirety.
Then we need to get the last element of each remaining row.
Then we need to get the remaining elements of the bottom row in reverse.
Then we need to get the first element of the remaining rows from the bottom up.
Finally, we use recursion to repeat the whole thing IF there are any remaining elements until we have all of them.

The following image can help visualizing the patterns. We start from 1 and work our way through the matrix:

Alright, let’s get to work

Step 0: let’s build the function’s skeleton

This is pretty much self explanatory. We just need to write a function that serves as the scaffolding for our work:

// Wel'll use this variable to fill with the numbers we're going to take from our matrix:
let endResult = [];
unrollMatrix = (array) => {
// This is our condition to check for any remaining elements and break out of recursion and give us the end result
if(array.length === 0) {
        console.log(endResult.join(', '));
        return;
    }
// 1.- Get the top row
// 2.- Get the last element of all remaining rows
// 3.- Get what's left of the bottom row in reverse
// 4.- Get the first element of any remaining rows
// 5.- Make the function call itself over whatever's left of our original matrix
}

Pretty simple stuff. The check at the top means "Keep working until there’s nothing, and when that happens, print all the numbers as a plain list of strings".

Step 1: Get the top row:

This is as straightforward as it gets. All we have to do is shift and then push our matrix to the endResult array. By using the spread operator, we make sure to "escape" the array and get the bare numbers. Remember we are working with an array of arrays and if we were to omit the spread operator, we would get the first row as an array:

endResult.push(...array.shift());

It’s important to keep track of what’s going on, so keep in mind that both endResult and our original matrix contain different values than what we started with, so at this point, endResult is an array:

endResult: Array(4) [ 1, 2, 3, 4 ]

While our original matrix "lost" the first row when we shifted it:

matrix: Array(3)  [[5,   6,  7,   8],
                   [9,  10, 11,  12],
                   [13, 14, 15,  16]];

Step 2: Get the last element of all remaining rows

So far we managed to get the first row and now we need the "right side" of our matrix. This means 8, 12 and 16. For this one, we need to write a quick loop to iterate over any remaining arrays, get their last element and push it to our endResult variable:

for(piece of array){
        endResult.push(piece.pop());
}

WHOA, what’s going on here? Fear not, this is just more concise way of writing a for loop. It was introduced in ES2015 and it ditches any counters and conditions to iterate through an object. Check this MDN article for a more in depth look.
Back to our example, we are going to iterate through the arr object and on each iteration, its components are going to be called "piece". So for every "piece" in our original matrix, we are going to pop their last element and push it into our endResult variable.
Progress check: Our endResult variable should look like this:

endResult: Array(7) [ 1, 2, 3, 4, 8, 12, 16 ]

And our original matrix should look this:

matrix: Array(3)  [[5, 6, 7],
                   [9, 10, 11],
                   [13, 14, 15,]];

Step 3: Get what’s left of the bottom row in reverse

We’re halfways there! We now need to get the bottom row in reverse so that means 15, 14 and 13. All we need to do is call our matrix with the spread operator, pop the last element and push it into our endResult in a reverse fashion:

endResult.push(...array.pop().reverse());

Pretty simple. This is just like the first step, only this time we’re using pop() to get the last element instead of the first one and then pushing it with reverse().
Progress check: endResult should now look like this:

endResult: Array(10) [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13 ]

And our matrix should look this:

matrix: Array(2)  [[5, 6, 7],
                   [9, 10, 11]];

Step 4: Get the first element of any remaining rows

We’re almost there! For this last step, we need to get the first element of each remaining array from the bottom up, which in our case would be 9, 5. To do so, we just need to map over our arrays, call shift() on them and push them into endResult in reverse:

endResult.push(...array.map(arr => arr.shift()).reverse());

Our function is almost ready and endResult should now look like this:

endResult: Array(12) [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5 ]

And our matrix should look this:

matrix: Array(2)  [[6, 7],
                   [10, 11]];

Now all we need to do is make the function call itself over whatever’s left of our original matrix:

unrollMatrix(array);

And we are done! If your exit condition works fine, you should get the expected result:

1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10

Room for improvement

Just because our function works doesn’t mean we’re done. We need to keep our time complexity in check, and so far, our function is comprised of four main operations. Let’s take a look at them and see where we can improve:

endResult.push(...array.shift());
This is O(1), we're good.
for(piece of array){
        endResult.push(piece.pop());
}

This is O(n), We’re good, but not really.

endResult.push(...array.pop().reverse());

This is O(1), so we’re good.

endResult.push(...array.map(arr => arr.shift()).reverse());

And lastly, this one is also O(1), so we’re still good.

So for the most part, our function is good. If we had no alternative, a time complexity of O(n) is totally fine, but if there is room to go from O(n) to O(1), then by all means we should attempt to do it:

endResult.push(...array.map(arr => arr.pop()))

By just getting rid of the for loop, we managed to simplify the inner workings of our function, and thus decreasing our time complexity to O(1). We could have done it like this from the beginning, but I believe keeping track of our time complexity is equally as important as making our function work. Keep in mind that systems are scalable, so just because it works fine in our computer doesn’t mean it’ll run fine with a larger data set in a real life environment.

The final code

const matrix = [[1,   2,  3,   4],
                [5,   6,  7,   8],
                [9,  10, 11,  12],
                [13, 14, 15,  16]];
let endResult = [];
unrollMatrix = (array) => {
// This is our condition to check for any remaining elements and break out of recursion and give us the end result
if(array.length === 0) {
        console.log(endResult.join(', '));
        return;
    }
    // 1.- Get the top row
    endResult.push(...array.shift());
    // 2.- Get the last element of all remaining rows
    endResult.push(...array.map(arr => arr.pop()));
    // 3.- Get what's left of the bottom row in reverse
    endResult.push(...array.pop().reverse());
    // 4.- Get the first element of any remaining rows
    endResult.push(...array.map(arr => arr.shift()).reverse());
    // 5.- Make the function call itself over whatever's left of our original matrix
    unrollMatrix(array);
}
unrollMatrix(matrix); // 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10

John Fajardo