Unrolling Matrix Walkthrough - JS
Tags: javascript, beginners, tutorial
Published: 2019-08-09 20:06:13

---
title: Unrolling Matrix Walkthrough - JS
published: true
description: A general walkthrough to "unroll" a 2-d Array
tags: #javascript #beginners #tutorial
---
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!