Rotate Matrix by 90 degrees clockwise Inplace

Rotate square matrix by 90 degrees Inplace OR
Turn an 2D array by 90 degree OR

Rotate a two dimensional array OR
Given N*N matrix, rotate it by 90 degree to left and right without extra memory

Rotate square matrix by 90 degrees Inplace.
Lets understand the problem statement graphically and it will be more clear,  


Algorithm


 There are 2 ways to Rotate a Matrix by 90 degrees
  1. In Place.
  2. Using extra Memory.

 We already saw how to Rotate a Matrix using extra memory:
Rotate Matrix by 90 degrees using Extra memory.

 

In this post, we will focus on Rotating a Matrix by 90 degrees Inplace.

For Rotating a matrix to 90 degrees in-place, it should be a square matrix that is same number of Rows and Columns otherwise inplace solution is not possible and requires changes to row/column.

It is very easy to solve this problem if it is well understood.  

For rotating a matrix to 90 degrees, we will start rotating it Layer by Layer.
Rotate first outer layer by 90 degrees, Rotate 2nd inner layer by 90 degree, Rotate 3rd inner layer by 90 degree and so on,


We will further break the problem of Rotating each layer to rotate each cell of layer by 90 degrees.
Starting from Left most cell of a Layer 1, we will first rotate it to 90 degrees and move to its correct position.
Pick second cell of layer 1 and rotate it to 90 degrees and move to its correct position and so on.


After 1st iteration, Layer 1 will be completely rotated to 90 degrees.
Now pick Layer 2 and repeat the same process.

In each Iteration, we are working on complete outer layer consisting of 2 rows 
(Example: Row 0 and Row 4 for Layer 1)
So, while coding we need to take care of this and need to iterate our outer loop from 0 to rowLength/2 and not till rowLength.
for (int i = 0; i <= (length)/2; i++)

For Inner loop, it should starts from where outer loop starts and decrements end layer in each iteration because in each iteration, Left wall and Right wall of matrix is getting rotated, so no need to touch it in next iteration.
 
for (int j = i; j < length-i; j++) {

First we will collect data of all 4 cells that forms 90 degrees and needs to be rotated, later we will swap it to 90 degree location.

Example:  While rotating first cell of Layer 1, we need to do following operations.
Data at cell at (0,0) need to be moved to cell (0,4). 
Data at cell at (0,4) need to be moved to cell (4,4).
Data at cell at (4,4) need to be moved to cell (4,0).
Data at cell at (4,0) need to be moved to cell (0,0).

Pick 2nd cell of Layer 1 and identify corresponding 90 degree location of all 4 cells and swap it location.
continue operation for all cells of Layer 1.

After Layer 1 is rotated, We need to work on Layer 2 but before starting to work on Layer 2, 
we need to increment our outer layer to start from next row and inner layer also to start from next row and end at rowLength-1 as Right wall of Matrix is already rotated in Layer 1 rotation.

Pick Layer 2 and repeat the process.

Java Program to Rotate a Matrix by 90 degrees Clockwise


package matrix;

public class RotateMatrixBy90Degree {

 public static void main(String[] args) {
  new RotateMatrixBy90Degree();
 }

 public RotateMatrixBy90Degree() {
  int[][] matrix = {
   {1,  2,  3,  4},
   {5,  6,  7,  8},
   {9,  10, 11, 12},
   {13, 14, 15, 16}
  };
  rotateMatrixInplace(matrix);
  printMatrix(matrix);
 }

 public void rotateMatrixInplace(int[][] matrix) {
  int length = matrix.length-1;
  
  for (int i = 0; i <= (length)/2; i++) {
      for (int j = i; j < length-i; j++) {
       
       //Coordinate 1
       int p1 = matrix[i][j];
       
       //Coordinate 2
       int p2 = matrix[j][length-i];
       
       //Coordinate 3
       int p3 = matrix[length-i][length-j];
       
       //Coordinate 4
       int p4 = matrix[length-j][i];
       
       //Swap values of 4 coordinates.
       matrix[j][length-i] = p1;
       matrix[length-i][length-j] = p2;
       matrix[length-j][i] = p3;
       matrix[i][j] = p4;
      }
  }
 }

 private static void printMatrix(int[][] matrix){
  for (int i = 0; i < matrix.length; i++) {
   for (int j = 0; j < matrix[0].length; j++) {
    System.out.print(matrix[i][j] + " "); 
   }
   System.out.println();
  }
 }
}



You may also like to see


Rotate N*M matrix by 90 degree


Print Matrix in Spiral order (Iterative way)

Transpose of M*N Matrix in Java

Count zeros in a row wise and column wise sorted matrix

Find middle element of a linked list

Union and Intersection of Two Sorted Arrays

Merge two sorted arrays in Java

How is ambiguous overloaded method call resolved in java


Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Post a Comment