In this article, we will look into another interesting problem related to 2D Arrays. Given a Matrix of N X N Dimension we have to Rotate matrix by 90 degrees. We will perform Rotation both Clockwise i.e. Right Rotation and Anti-Clockwise i.e. Left Rotation respectively. We will discuss each operation in detail along with a hint to perform Rotation of Matrix K times.
Note: To Perform Any type of Rotation, The Matrix should have equal dimensions (N X N) i.e. No. of Rows in Matrix = No. of Columns in Matrix.
Table of Contents
Clockwise or Right Rotate a Matrix
In this type, we need to Right Rotate the given N X N Matrix by 90 degrees. Let us understand this with an example:
Basically, we need to start from the last row in the Original Matrix and need to make each row as a column to rotate the matrix in Clockwise direction.
So, let us look at the approach to do this :
- We will first transpose of given matrix or 2D Array. By Transpose, we mean each Row of the matrix becomes a Column and vice-versa. In simple words, each Element in ith row is replaced by corresponding element in the ith column. We will do this in code by Swapping the elements at the ith row and column respectively. So, considering the above matrix the Transpose will be:
- After doing transpose, we need to just reverse the contents/elements of each row. Since each Row of the matrix is a 1D Array itself, we just reverse each array or row after that we would have the Right Rotated Matrix. So after reversing the Transpose Matrix we get the result.
Implementation in Java
Now, let us look at the code to cover this approach considering the same example as discussed above.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
public class RotateMatrix { // Takes Matrix and Size of Matrix and performs Clockwise or Right Rotation by 90 degrees. static void rightRotate(int matrix[][],int n) { //At first we perform transpose of the matrix //by swapping elements of every i'th row with j'th column for(int i=0;i<n;i++) { for(int j=i;j<n;j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } // Then we reverse the elements of each row. for(int i=0;i<n;i++) { // Logic to reverse each row i.e 1D Array. int low = 0; int high = n-1; while(low < high) { int temp = matrix[i][low]; matrix[i][low] = matrix[i][high]; matrix[i][high] = temp; low++; high--; } } System.out.println("The Right Rotated Matrix is: "); for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { System.out.print(matrix[i][j]+" "); } System.out.println(); } } public static void main(String args[]) { int n=3; // Creating a 3 X 3 matrix. int matrix[][] = new int[][]{ {1,2,3}, {4,5,6} , {7,8,9} }; System.out.println("The Original Matrix is: "); for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { System.out.print(matrix[i][j]+" "); } System.out.println(); } rightRotate(matrix,n); } } |
Output:
|
1 2 3 4 5 6 7 8 9 10 |
The Original Matrix is: 1 2 3 4 5 6 7 8 9 The Right Rotated Matrix is: 7 4 1 8 5 2 9 6 3 |
Time Complexity: The time complexity of performing rotation is O(n2) as we traverse all the elements of the matrix while interchanging them.
Further reading:
Anti-Clockwise or Left Rotate a Matrix
In this type, we need to Left Rotate the given N X N Matrix by 90 degrees. Let us understand this with an example:
Basically, we need to start from the last row in the Original Matrix and need to make each column as a row to rotate the matrix in anti clockwise direction.
So, let us look at the approach to do this :
- Like the approach we followed above in Right Rotate, we will first transpose the given Matrix or 2D Array. We convert elements of each Row of the matrix becomes a Column and vice-versa. So, considering the above matrix the Transpose will be:
- After getting the transpose, Instead of reversing the Rows like we did in Right Rotate, Here we reverse contents of each Column in the Matrix. After doing this, we will have our resultant Left Rotated Matrix:
Now let us look at the implementation in code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
public class RotateMatrix { // Takes Matrix and Size of Matrix and performs Anti - Clockwise Rotation by 90 degrees. static void leftRotate(int matrix[][],int n) { //At first we perform transpose of the matrix //by swapping elements of every i'th row with j'th column for(int i=0;i<n;i++) { for(int j=i;j<n;j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } // Then we reverse the elements of each column. for(int i=0;i<n;i++) { // Logic to reverse each column int low = 0; int high = n-1; while(low < high) { int temp = matrix[low][i]; matrix[low][i] = matrix[high][i]; matrix[high][i] = temp; low++; high--; } } System.out.println("The Left Rotated Matrix is: "); for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { System.out.print(matrix[i][j]+" "); } System.out.println(); } } public static void main(String args[]) { int n=3; // Creating a 3 X 3 matrix. int matrix[][] = new int[][]{ {1,2,3}, {4,5,6} , {7,8,9} }; System.out.println("The Original Matrix is: "); for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { System.out.print(matrix[i][j]+" "); } System.out.println(); } leftRotate(matrix,n); } } |
Output:
|
1 2 3 4 5 6 7 8 9 10 |
The Original Matrix is: 1 2 3 4 5 6 7 8 9 The Left Rotated Matrix is: 3 6 9 2 5 8 1 4 7 |
Time Complexity: The time complexity for this type is also O(n2).
How to Rotate Matrix K Times?
Now if we want to Rotate a matrix K times, Depending on the type of rotation just call the rightRotate() or leftRotate() method inside a loop K times and print the matrix once like this:
|
1 2 3 4 5 6 7 8 9 |
int k = 3; while(k>0) { leftRotate(matrix,n); // Remove Print logic from the method before calling k--; } //Then Print Matrix |
So that’s all about how to Rotate Matrix by 90 degrees in java. You can try out the code with different examples and let us know your queries.
