Rotate image (square matrix) by 90 deg

Given an image. How will you rotate the image by 90 degrees anti-clockwise.

Original Image	Rotated Image

A rectangular image can be thought of as a two dimensional matrix.

The problem of rotating an array reduces to rotating a two-dimensional matrix where we are supposed to rotate the values of cells by 90 degrees anti-clockwise.

For example

Input Matrix:
      1  2  3
      4  5  6
      7  8  9
Output:
      3  6  9
      2  5  8
      1  4  7

The brute-force solution is very simple using an extra 2-dim array to store the rotated copy of the matrix. The i^th row in the original array will become the i^th column in the rotated matrix as shown in the code below:

class RTDemo
{
  public static void rotate(int[][] arr)
  {
    // TEMPORARY MATRIX TO HOLD ROTATED ARRAY
    int[][] temp = new int[arr.length][arr[0].length];
    
    int n = arr.length;
    for(int i=0; i<n; i++)
    {
      for(int j=0; j<n; j++)
      {
        temp[j][n-i-1] = arr[i][j];
      }
    }

    // COPY MATRIX
    for(int i=0; i<n; i++)
      for(int j=0; j<n; j++)
        arr[i][j] = temp[i][j]; 
  }
  public static void printArray(int[][] arr)
  {
    for(int i=0; i<arr.length; i++)
    {
      for(int j=0; j<arr[0].length; j++)
        System.out.print(arr[i][j] + " ");

      System.out.println("");
    }

  }
  public static void main(String[] obj)
  {
    int[][] arr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}} ;
    printArray(arr);
    rotate(arr);
    System.out.println("\nAFTER ROTATION :");
    printArray(arr);
  }
}

When we run the above program the output window looks like below:

Obviously, this approach takes a lot of extra space.

In-Place Solution:

To solve the question without any extra space, rotate the array in form of squares, dividing the matrix into squares or cycles. For example,

A 4 X 4 matrix will have 2 cycles. The first cycle is formed by its 1st row, last column, last row and 1st column. The second cycle is formed by 2nd row, second-last column, second-last row and 2nd column. The idea is for each square cycle, swap the elements involved with the corresponding cell in the matrix in anti-clockwise direction i.e. from top to left, left to bottom, bottom to right and from right to top one at a time using nothing but a temporary variable to achieve this.

First Cycle (Involves Red Elements) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Moving first group of four elements (First elements of 1st row, last row,

1st column and last column) of first cycle in counter clockwise. 4 2 3 16 5 6 7 8 9 10 11 12 1 14 15 13

Moving next group of four elements of first cycle in counter clockwise 4 8 3 16 5 6 7 15 2 10 11 12 1 14 9 13

Moving final group of four elements of first cycle in counter clockwise 4 8 12 16 3 6 7 15 2 10 11 14 1 5 9 13

Second Cycle (Involves Blue Elements) 4 8 12 16 3 6 7 15 2 10 11 14 1 5 9 13

Fixing second cycle 4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13

Algorithm:

There is N/2 squares or cycles in a matrix of side N.

Process a square one at a time. Run a loop to traverse the matrix a cycle at a time, i.e loop from 0 to N/2 – 1, loop counter is i Consider elements in group of 4 in current square, rotate the 4 elements at a time.

So the number of such groups in a cycle is N – 2*i. So run a loop in each cycle from x to N – x – 1, loop counter is y The elements in the current group is (x, y), (y, N-1-x), (N-1-x, N-1-y), (N-1-y, x), now rotate the these 4 elements, i.e (x, y) <- (y, N-1-x), (y, N-1-x)<- (N-1-x, N-1-y), (N-1-x, N-1-y)<- (N-1-y, x), (N-1-y, x)<- (x, y) Print the matrix.

Implementation:

// Java program to rotate a matrix by 90 degrees 
import java.io.*; 

class GFG { 
	// An Inplace function to rotate a N x N matrix 
	// by 90 degrees in anti-clockwise direction 
	static void rotateMatrix(int N, int mat[][]) 
	{ 
		// Consider all squares one by one 
		for (int x = 0; x < N / 2; x++) { 
			// Consider elements in group of 4 in 
			// current square 
			for (int y = x; y < N - x - 1; y++) { 
				// store current cell in temp variable 
				int temp = mat[x][y]; 

				// move values from right to top 
				mat[x][y] = mat[y][N - 1 - x]; 

				// move values from bottom to right 
				mat[y][N - 1 - x] = mat[N - 1 - x][N - 1 - y]; 

				// move values from left to bottom 
				mat[N - 1 - x][N - 1 - y] = mat[N - 1 - y][x]; 

				// assign temp to left 
				mat[N - 1 - y][x] = temp; 
			} 
		} 
	} 

	// Function to print the matrix 
	static void displayMatrix(int N, int mat[][]) 
	{ 
		for (int i = 0; i < N; i++) { 
			for (int j = 0; j < N; j++) 
				System.out.print(" " + mat[i][j]); 

			System.out.print("\n"); 
		} 
		System.out.print("\n"); 
	} 

	/* Driver program to test above functions */
	public static void main(String[] args) 
	{ 
		int N = 4; 

		// Test Case 1 
		int mat[][] = { 
			{ 1, 2, 3, 4 }, 
			{ 5, 6, 7, 8 }, 
			{ 9, 10, 11, 12 }, 
			{ 13, 14, 15, 16 } 
		}; 

		// Tese Case 2 
		/* int mat[][] = { 
							{1, 2, 3}, 
							{4, 5, 6}, 
							{7, 8, 9} 
						}; 
		*/

		// Tese Case 3 
		/*int mat[][] = { 
						{1, 2}, 
						{4, 5} 
					};*/

		// displayMatrix(mat); 

		rotateMatrix(N, mat); 

		// Print rotated matrix 
		displayMatrix(N, mat); 
	} 
}

Time Complexity : O(n*n), where n is side of array, A single traversal of the matrix is needed.

Space Complexity : O(1), constant space is needed

Exercise: Turn 2D matrix by 90 degrees in clockwise direction without using extra space.

Rotate a matrix by 90 degree without using any extra space | Set 2