Title:
Rotate Image
Link to LeetCode:
https://leetcode.com/problems/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],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);
}
}