Problem - Write an algorithm capable of rotating a matrix, in-place without any auxiliary storage.
I don't have an elaborate thought process to develop this algorithm. It's a few rules you ought to remember to implement rotations in the matrix.
To implement these rules, you need some helper functions which are quite simple really. You need to be able to transpose a matrix, reverse a row, reverse a column. That's it. The rest is just a combination of these 3 functions.
Note : These functions create copies of the matrix, we can design algorithms that modify the original matrix with ease for square matrices. For non-square matrices, we have to create new matrices.
Okay, let's get to the rotations. So we need to perform three kinds of rotations. 90,180,270.
1) Rotation by 90/-270 degrees
- Transpose the Matrix
- Reverse each row
2) Rotation by 180/-180 degrees
There are two methods:
First Method, is clearly obvious, perform 90 degree rotation twice.
Second Method contains two steps, both these operations can be done in any order,
- Reverse Each Row
- Reverse Each Column
3) Rotation by 270/-90 degrees
- Transpose the matrix
- Reverse each column
You can find the entire source code here.
Comments
Post a Comment