Unrolling Matrix Walkthrough - JS

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!