Exercise: Matrix Rotation

Inside the directory you created for this course on JavaScript, create a new folder called Exercise-29-Matrix-Rotation and put the .html solution files for this exercise within it.

The function is only meant to rotate the matrix by ::90^{\circ}::, and is likewise quite straightforward to implement.

Well, even if we were asked to rotate the matrix by an arbitrary angle, it would still be easy to implement the function in that case. This follows from the fact that there possibly could only be three different angles to consider when rotating a matrix i.e. the angles ::90^{\circ}::, ::180^{\circ}:: and ::270^{\circ}::. That's it.

Any other angle, be that a negative angle such as ::-90^{\circ}::, would eventually resolve down to any one of these three angles and so we could simply call our rotateBy90() function multiple times to rotate to that given angle.

Anyways, let's talk about the simple implementation of rotation by ::90^{\circ}:: as performed by our rotateBy90() function.

The solution is merely about figuring out a pattern in the final rotated matrix based on the initial configuration of the matrix and then translating that pattern into actual code.

Let's think about that pattern...

Where does the ::(i, j)^{th}:: element of the rotated matrix come from the original matrix?

Well, it can easily be observed that anything that is in the ::i^{th}:: row of the rotated matrix lies somewhere in the ::i^{th}:: column of the original matrix.

Secondly, anything that's in the ::j^{th}:: column of the rotated matrix lies somewhere in the ::(n - j - 1)^{th}:: row of the original matrix (assuming that ::i:: begins at ::0::, and not at ::1::).

This means that the ::(i, j)^{th}:: element of the rotated matrix is simply the ::(n - j - 1, i)^{th}:: element of the original matrix.

Voila!

This result provides us with the solution to this exercise. Now what's left is just to convert it to a piece of code. That's it.

Let's do that.

The function definition below of rotateBy90() goes over the given array matrix, iterates over each of its items and performs the assignment as described above:

function rotateBy90(matrix) {
    var n = matrix.length;
                    
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            matrix[i][j] = matrix[n - j - 1][i];
        }
    }

    return matrix;
}

Now, let's test this code on the two arrays given in the description of this exercise above:

rotateBy90([[1, 4], [10, 2]])

[[10, 10], [2, 10]]

rotateBy90([[3]])

[[3]]

Oops! The output of the first log is not what we expected. There is definitely some problem in the code.

Can you spot the problem?

Well, the problem lies in line 6. What do you think is the problem in line 6?

Let's start by going through the loop manually on the following matrix,

and see each iteration closely.

The given matrix is [[1, 4], [10, 2]]. Its length is 2. Likewise, n = 2.

In the very first iteration of the inner loop (in line 5), i = 0 and j = 0. matrix[i][j] thus becomes matrix[0][0]. This position is assigned the value of matrix[n - j - 1][i] i.e. matrix[1][0] that is the number 5.

At the end of this first iteration, matrix is [[10, 4], [10, 2]].

Let's move on. (The problem is already apparent at this stage!)

Next, i = 0 and j = 1. matrix[i][j] thus becomes matrix[0][1]. This position is assigned the value of matrix[n - j - 1][i] i.e. matrix[0][0] that holds the number 10.

And here's our problem.

When we assign a value to matrix[i][j] in the first iteration, we have, in effect, changed what was previously there. For the second iteration, matrix[i][j] wants to obtain the value of matrix[0][0] which should've been 1 in order for the operation to work correctly, however it turns out to be 10.

Hence, the second iteration assigns 10 to matrix[0][1]. You could repeat this manual iteration for the matrix upto the end and you'll clearly see that the output is wrong.

So, any solutions to this?

Well, for the solution we first ought to think about the underlying cause of the problem.

When we assign a value to matrix[i][j] inside the inner loop, we effectively lose the information that was previously stored in that position. On subsequent iterations, even though we perform the correct positional substitutions, the actual values substituted are incorrect as they've been changed from previous iterations.

The solution to this is simply to presence the original matrix passed to us by making a copy of it and perform the assignments to the original matrix (figuring out values for each assignment from this copied matrix).

Simple!

In the code below, we have rewritten the rotateBy90() function:

function rotateBy90(matrix) {
    var n = matrix.length;
    var matrixCopy = [];

    for (var i = 0; i < n; i++) {
        matrixCopy.push([]); // add a row
        for (var j = 0; j < n; j++) {
            matrixCopy[i].push(matrix[i][j]); // add new entry
        }
    }
                    
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            matrix[i][j] = matrixCopy[n - j - 1][i];
        }
    }

    return matrix;
}

First, we make a copy of the the given matrix and save that copy in the local variable matrixCopy. Next, we go with our old nested for loop performing the rotation.

The only change in this part of the function's definition is where we obtain the value to be put in matrix[i][j] from — that is, from the matrixCopy array.

In this way, we know that the assignment made in each iteration is of the correct value.

As before, let's test this code to confirm its correctness:

rotateBy90([[1, 4], [10, 2]])

[[10, 1], [2, 4]]

rotateBy90([[3]])

[[3]]

Perfect!

Now, it's working. You could even try to test this function on a ::3 \times 3::, ::4 \times 4::, ::5 \times 5::, or any ::n \times n:: matrix — the output would always be correct.