how to rotate a matrix in javascript

How To Rotate A Matrix In JavaScript?

by

Rotating a matrix is one of the basic exercises for Data Structures and Algorithms, especially arrays. Matrix is a 2-Dimensional array after all. So, given a mxn 2-Dimensionanal matrix, how can you rotate a matrix in JavaScript? Here is the solution

// rotate the matrix by 90 degrees right
function rotateMatrix(mtx) {
    const len = mtx.length;

    for (let x = 0; x < len/2; x++) {
        for (let y = x; y < len-x-1; y++) {
            let temp = mtx[x][y];

            // copy element from bottom left to top left
            mtx[x][y] = mtx[len-y-1][x];

            // copy element from bottom right to bottom left
            mtx[len-y-1][x] = mtx[len-x-1][len-y-1];

            // copy element from top right to bottom right
            mtx[len-x-1][len-y-1] = mtx[y][len-x-1];

            // copy element from top left to top right
            mtx[y][len-x-1] = temp;
        }
    }

}

The solution’s simple but might be confusing at first. So, let me walk you through it.

(Note : to be specific, we are rotating a mxn 2-Dimensional array by 90 degrees to the right, algorithms might differ for different dimensions and different directions)

By the way, check this out if you need a definition for what a matrix is. (No, it’s not the movie with Keanu Reeves in it)

We can break the algorithm down to 3 main parts :

  1. Iterating to half the length of the outer array (the outer loop)
  2. Iterating the inner array
  3. Moving the elements

Before we dive into the steps, let me give you a study case to understand how the algorithm works better.

3x3 matrix example
3×3 matrix example

Here we have a 3×3 matrix example.

Part 1 – The outer loop

Since it is a nested array, we’d need nested loops to iterate through the elements. For the outer loop, we use for (let x = 0; x < len/2; x++). It’s just a normal loop except that we are looping only until half the outer array length. So if we have a 3×3 matrix, the loop will run twice.

We only loop through to half of the outer array because we’re doing a rotation. We’re essentially switching elements from one side to the opposite side. If you’re swapping 4 items, you’ll only do it 2 times, right? So we do it to avoid re-rotating the elements.

So, following the study case, we’ll loop through [1, 2, 3] and [4, 5, 6]

Part 2 – The inner loop

We’ll be doing the inner loop with for (let y = x; y < len-x-1; y++). So, we’ll be looping starting from y = outer loop iteration to outer array length decreased by outer loop iteration and 1.

The reasoning for the odd number of loops is the same as the outer loop, we want to avoid re-rotating the elements.

In the study case, we’ll be looping through :

  • [1] and [2] for the first outer loop
  • [ ] for the second outer loop. The outer loop requirement is achieved, but the conditions aren’t passed for the inner loops.

In the end, there are 2 activities done in the loops.

Part 3 – Moving the elements

In a loop, we’ll be moving 4 elements at a time. If you look at the matrix, you’ll notice there are actually only 8 elements that need to be rotated since the center is already in the correct position. So, we’ll be doing 2 loops.

We’re moving the loops by copying the elements to each other and also with a temporary variable. Look back to the code and you’ll see that we’re copying each element from a specific position to each other.

In the study case, the 2 loops done are as follows.

First, we rotate the corners, [1, 3, 9, 7]

first rotation
First rotation

Then, we rotate [4, 2, 6, 8].

second rotation
Second rotation

And finally, our matrix is fully rotated.

Note

You’ll notice that there’s no return statement in the function. It’s because JavaScript is reference-based. So, it alters the original matrix directly.

Tips

To help you debug, I recommend logging the matrix at the step you’re confused about to see the matrix at that step.

But, as I tried logging, I’ve noticed that since JavaScript arrays are reference based, we’ll need a workaround to log the matrix which is shown below.

console.log(JSON.parse(JSON.stringify(mtx)));

Complexity

Time Complexity : O(mn)

We’re looping through most of the elements of the matrix. m is the row length and n is the column length.

Space Complexity : O(1)

We’re only using one array without creating a new array.

Summary

We basically loop the elements and switch between them. Hope that breakdown and visualization helps.

To understand it better, try visualizing a 4×4 matrix.

Since matrix is basically a nested array, it’ll be helpful to learn more about JavaScript Arrays With Big O Complexities!

For you who want to brush up your JavaScript skills, whether to deepen or learn form zero, I recommend you try Codecademy. There are tons of JavaScript lessons that you can learn in a structured and interactive way. You can learn from the most basic materials to advanced stuffs and even preparing for technical interviews. Go try it now!

If you have a better solution be it code-wise or efficiency-wise, please do comment below!

Check out the rest of my blog for more helpful contents on Data Structures and Algorithms in JavaScript!

See you next post!

Leave a Comment