Course: JavaScript

Progress (0%)

# Exercise: Matrix Rotation

Exercise 32 Average

Prerequisites for the exercise

1. JavaScript Array Methods
2. JavaScript Arrays Basics
3. All previous chapters

## Objective

Rotate a given matrix clockwise by 90°.

## Description

In the world of matrices, a square matrix is a $n \times n$ matrix i.e. it has $n$ rows and $n$ columns.

Shown below are a couple of square matrices, along with their dimensions:

$\begin{bmatrix} 1 & 4 \\ 10 & 2 \end{bmatrix}$
$2 \times 2$
$\begin{bmatrix} 1 & 5 & 2 \\ 0 & 6 & 3 \\ 6 & 15 & 1 \end{bmatrix}$
$3 \times 3$
$\begin{bmatrix} 1 & 9 & 0 & 2 \\ -51 & 2 & 3 & 2 \\ -1 & 16 & -5 & 2 \\ 1 & 90 & 10 & 6 \end{bmatrix}$
$4 \times 4$

When dealing with square matrices, matrix rotation is a useful operation.

As the name suggests, matrix rotation reorders items of the matrix such that the matrix seems to literally have been rotated.

The rotation angle is usually $90^{\circ}$, but it can be any multiple of $90$, for e.g. $180$, $270$, $-90$ etc.

The sign of the angle determine the direction of rotation: positive means clockwise and negative means counter-clockwise. For e.g. $90^{\circ}$ means to rotate the matrix by $90^{\circ}$ clockwise, while $-90^{\circ}$ means to rotate the matrix by $90^{\circ}$ counter-clockwise.

For instance, if we were to rotate the matrix below by $90^{\circ}$,

$\begin{bmatrix} 1 & 4 \\ 10 & 2 \end{bmatrix}$

then we'd get the following configuration:

$\begin{bmatrix} 10 & 1 \\ 2 & 4 \end{bmatrix}$

Here's a visual animation to help you see the rotation much better:

1
4
10
2

As you can see, at the end of the rotation, the positions of the elements of the matrix have effectively been changed. Neither is any new element added, nor is any existing element deleted — the rotation is simply a change of the order of values.

Now, if we see this rotation operation from the perspective of a programmer we could see a pattern it. That is, we could discretely list out the steps to be taken in order to rotate a matrix by a given angle (a multiple of $90$) using a computer program.

In this exercise, you have to create a function rotateBy90() that rotates a given matrix by $90^{\circ}$.

The function has the following signature:

function rotateBy90(matrix) {
}

It should mutate the original matrix array passed to it and then finally return it in its rotated configuration.

Shown below are a couple of examples of how rotateBy90() should behave:

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

## New file

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

## Solution

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.

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,

$\begin{bmatrix} 1 & 4 \\ 10 & 2 \end{bmatrix}$

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++) {
for (var j = 0; j < n; j++) {
}
}

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.

"I created Codeguage to save you from falling into the same learning conundrums that I fell into."

— Bilal Adnan, Founder of Codeguage