2-Dimensional Matrix Rotation in JavaScript
Recently, I came across a problem to rotate a 2 dimensional matrix 90 degrees clockwise using an extra space (i.e. using additional memory).
Let us understand clockwise rotation first and we will be doing anticlockwise rotation in no time!
Rotation of a 3x3 matrix 90 degrees clockwise looks something like this:
Basically, columns become rows and rows become columns. Considering that the source matrix has dimension of MxN. The destination matrix has a dimension of NxM. It may not be obvious here since we are taking a square matrix, but take a non-square matrix and see it for yourself.
One thing to note is that 1st row in the source matrix becomes the last column in the destination matrix, 2nd row becomes 2nd last column and so on... (i.e. rows are reversely transformed into columns).
Let us see how the indices of elements in the matrix change:
I already see a pattern emerging here, don’t you? From the diagram above, we can deconstruct the relationship between the indices of elements in source matrix and the destination matrix as:
Here, we are flipping rows and columns (i.e. transposing the matrix) but also accounting for the fact that the rows are in reverse order. 1 is subtracted from N-j since we are using 0-based indexing of arrays.
Enough chit-chat, lets code this thing…
First of all, we need to create an empty destination matrix.
Then, we start copying the corresponding elements of the source matrix into the destination matrix.
The complete code looks like this:
Now that we performed clockwise rotation, counter-clockwise rotation is just the reverse (i.e. flip columns and rows) but account for the fact that the last column in the source matrix is the first row, 2nd last column is the 2nd row and so on… (i.e. columns are transformed in reverse order) in the destination matrix. So, the relationship between elements will be:
Not so hard now, is it? Kudos to you for keeping up with me.
Final Thoughts
Matrix rotation is trivial once we get a understanding of how the elements of the matrix are transformed. I stumbled upon this problem and thought that this approach might help others. I will write about in-place rotation soon.
P.S.: This is my first article. Please let me know if I need to improve anything. My mission is to learn and let learn. XD.
