# Unrolling Matrix Walkthrough - JS

### Kim Heidorn γ»5 min read

As Iβve been starting my job search, I have been grinding LeetCode problems, tackling all the algorithm practice I can to ease my nerves going into technical interviews. I have been coding in JavaScript and have been doing my best to master the βMatrixβ problems. Below are the steps I took to traverse the matrix in an *unrolling* fashion.

### The Problem

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

Assume that Input will always be an even matrix, (i.e. 2 x 2, 3 x 3, 6 x 6, etc.)

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

### Brute Force Option and Big O

The first step, for me, is to always follow my first instinct and get the brute force option to work. I knew from a previous project that I had built a grid (aka matrix) using two nested `for-loops`

to step through each cell. While this is clearly not the best solution (runtime: O(n^{2)),} I knew it to be the first way to solve it. Had the runtime Big O been O(n), I likely would have continued down this path, but I wanted to try to solve this problem with a more unique solution.

### Refactor Code

Now, I had not really written any code for the above *brute force* option, so the title is a bit deceiving, but had I been in a real technical interview, I would have definitely wanted to refactor my *brute force* code. Instead, since this was just practice, I decided to really analyze the problem. The code wanted me to return the entire first row in the same order, the last index of the middle rows, the entire last row in reverse order, and finally, the first index of the middle rows. If I were to augment the original matrix and remove the values above, I would be left with an internal matrix that was reduced entirely by 2. For the example input above, the 4 x 4 matrix after the required removals would leave me with a 2 x 2 matrix. This new matrix would then need to be treated in a similar manner. Essentially, I had stumbled into a great recursive function exercise. It would still result in O(n^{2)} runtime, but at least more interesting from a challenge perspective.

### Break Up the Steps

I had a general game plan, but decided to start coding out the basic skeleton to my solution.

I knew with recursive functions I need to start with a `base case`

aka a case that tells my function to stop, and ending function that would call the function on itself. Also, I knew that the output was not an array, but instead a string. Thus, I need an `ending`

variable that initially was an empty string. Given that this was a recursive function, the string would also need to be an argument I would pass into the function, but would have an initial value of `ββ`

.

```
function unroll(matrix, endResult = ββ) {
//base case
if (matrix.length === 0) {
return endResult
}
//call itself
return unroll(matrix, endResult)
}
```

Not bad, but I realized pretty quickly I was missing on crucial detail, the `,`

to chain my recursive strings!

This made the new code:

```
function unroll(matrix, endResult = ββ) {
//base case
if (matrix.length === 0) {
return endResult
}
//call itself
return unroll(matrix, endResult + β, β)
}
```

Now it was time to start traversing the matrix. Again, I knew I should take this into individual steps. The first part would be to just printing the first row exactly as is. Given this was a nested array, I could either write `matrix[0]`

or `matrix.shift()`

. Personally, I wanted to get more comfortable using methods in my whiteboarding problems, so I went with the `matrix.shift()`

option. Now to convert this removed array to a string, I used `.join(β, β)`

remembering that I need to add in the correct punctuation.

```
function unroll(matrix, endResult = ββ) {
//base case
if (matrix.length === 0) {
return endResult
}
//top
endResult += (matrix.shift().join(β, β))
//call itself
return unroll(matrix, endResult + β, β)
}
```

Next would be to get the last two elements, or right elements, for **only** the middle rows. This would require a `for-loop`

in order to traverse into these nested arrays. There was no way I could solve this without it. In this scenario, since I am only taking individual inputs at one time, I did not need to add the `.join( β, β)`

method, and instead would need to add the required punctuation prior to adding the element. Also, since I wanted to continue using the method process, I used `.pop()`

to remove the last element.

```
function unroll(matrix, endResult = ββ) {
//base case
if (matrix.length === 0) {
return endResult
}
//top
endResult += (matrix.shift().join(β, β))
//right
for (let i = 0; i < matrix.length - 1; i++) {
endResult += β, β + (matrix[i].pop())
}
//call itself
return unroll(matrix, endResult + β, β)
}
```

The script for the bottom row was similar to the top row, but instead of `shift()`

, I need to use `pop()`

and `reverse()`

to reverse the resulting array.

```
function unroll(matrix, endResult = ββ) {
//base case
if (matrix.length === 0) {
return endResult
}
//top
endResult += (matrix.shift().join(β, β))
//right
for (let i = 0; i < matrix.length - 1; i++) {
endResult += β, β + (matrix[i].pop())
}
//bottom
endResult += β, β + (matrix.pop().reverse().join(β, β))
//call itself
return unroll(matrix, endResult + β, β)
}
```

To add the first elements of the middle rows to the `endResult`

string, I need to use a `for-loop`

. However, this time I need to do a `reverse for-loop`

counting down until the value of `i`

is equal to 0. I also need to use `shift()`

to remove the first element of the array I am iterating over.

```
function unroll(matrix, endResult = ββ) {
//base case
if (matrix.length === 0) {
return endResult
}
//top
endResult += (matrix.shift().join(β, β))
//right
for (let i = 0; i < matrix.length - 1; i++) {
endResult += β, β + (matrix[i].pop())
}
//bottom
endResult += β, β + (matrix.pop().reverse().join(β, β))
//left
for (let i = matrix.length -1; i >= 0; i--) {
endResult += β, β + (matrix[i].shift())
}
//call itself
return unroll(matrix, endResult + β, β)
}
```

I thought I was done, but I found an error in my script. The resulting string had two extra characters of `,`

that need to be removed. Using `.substring()`

and setting the arguments at `(0, endResult.length - 2)`

isolates and removes the last two characters to return the desired output.

The final script is

```
function unroll(matrix, endResult = ββ) {
//base case
if (matrix.length === 0) {
return (endResult.substring(0, endResult.length - 2))
}
//top
endResult += (matrix.shift().join(β, β))
//right
for (let i = 0; i < matrix.length - 1; i++) {
endResult += β, β + (matrix[i].pop())
}
//bottom
endResult += β, β + (matrix.pop().reverse().join(β, β))
//left
for (let i = matrix.length -1; i >= 0; i--) {
endResult += β, β + (matrix[i].shift())
}
//call itself
return unroll(matrix, endResult + β, β)
}
```

Voila! The matrix is unrolled! Hope you enjoyed the walkthrough and feel free to give input for improved methods!

Hi Kim, I've appreciated your exercise!

Anyway, because I love short writing I prefer to use functional methods and ES6.

Try this, for example:

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

console.log(arr);

console.log(arr.reduce((prev,curr,idx,[]) => [...prev,...curr]).toString());

Have a nice week end!