Title:

Rotate Image

Specification:

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).

Note:
You have to rotate the image in-place,
which means you have to modify the input 2D matrix directly.
DO NOT allocate another 2D matrix and do the rotation.

Examples:

Example 1:

Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

Example 2:

Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
rotate the input matrix in-place such that it becomes:
[ [15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

Initial Code and Signature:

``` public interface Rotater { public void rotate(int[][] matrix); } ```

Algorithm:

Main Idea: In a 90-degree rotation, element a[i,j] goes to element a [j, n-i],
where n is the number of the last column (or row).
Simply, for each element in the matrix, the element should be rotated.
1. Start from row 0.
2. For each element in the row except the last element perform a circular rotation:
1. a [row, j] -> a [j, n - 1 - row]
2. a [j, n - 1 - row ] -> a [n - 1 - row, n - 1 - j]
3. a [ n - 1 - row, n - 1 - j] -> a [ n - 1 - j, row]
4. a [ n - 1 - j, row] -> a [row] [j]
Now, all the elements in row 0, row n-1, col 0 and col n-1 are rotated. The matrix that should be rotated is bounded to row 0, col n-2, row n-2, col 0.
3. repeat the rotation for the new matrix (new bounds) until its dimension is < = 1.

Run-Time Analysis:

GitHub Project:

Code:

``` /** * * @author Mahsa Sadi * * @since 2020 - 03 - 07 * * License: Creative Commons * * Copyright by Mahsa Sadi * */ public class RotaterV3 implements Rotater { /** * * * Problem: Rotate Image * * Description: * You are given an n x n 2D matrix representing an image. * Rotate the image by 90 degrees (clockwise). * * * Note:You have to rotate the image in-place, * which means you have to modify the input 2D matrix directly. * DO NOT allocate another 2D matrix and do the rotation. * * Solution: * * Main Idea: * * In a 90-degree rotation, element a[i,j] goes to element a [j, n-i], * where n is the number of the last column (or row). * * Simply, for each element in the matrix, the element should be rotated. * * * * * 1- Start from row 0. * * 2- For each element in the row except the last element perform a circular rotation: * a [row, j] -> a [j, n - 1 - row] * a [j, n - 1 - row ] -> a [n - 1 - row, n - 1 - j] * a [ n - 1 - row, n - 1 - j] -> a [ n - 1 - j, row] * a [ n - 1 - j, row] -> a [row] [j] * * Now, all the elements in row 0, row n-1, col 0 and col n-1 are rotated. * The matrix that should be rotated is bounded to row 0, col n-2, row n-2, col 0. * * 3- repeat the rotation for the new matrix until its size is < = 1 ; */ @Override public void rotate(int[][] matrix) { rotateSquare (matrix, 0, matrix[0].length - 1 ); } public void rotateSquare (int [][] matrix, int start, int end) { int temp1 , temp2, k; for (int j = start; j < end; j++) { int rowToBeRotated = start; int colToBeRotated = j; temp1 = matrix [rowToBeRotated][colToBeRotated]; for (int i = 0; i < 4; i++) { temp2 = matrix [colToBeRotated][start + end - rowToBeRotated]; matrix [colToBeRotated][start + end - rowToBeRotated] = temp1; temp1 = temp2; k = rowToBeRotated ; rowToBeRotated = colToBeRotated; colToBeRotated = start + end - k; } } if ( (end - 1) - (start + 1) + 1 > 1 ) rotateSquare (matrix, start + 1, end - 1); } } ```