Rotate Image Problem: You are given an n x n
2D matrix
representing an image, rotate the image by 90 degrees (clockwise).
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.
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]]
Table of Contents
Rotate Image Problem Solution
Problem Solution In Python
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
lb = 0
ub = len(matrix) - 1
while(lb < ub):
for i in range(ub - lb):
self.swap(matrix, (lb, i + lb), (ub - i, lb))
self.swap(matrix, (ub - i, lb), (ub, ub - i))
self.swap(matrix, (ub, ub - i), (i + lb, ub))
ub -= 1
lb += 1
def swap(self, matrix, coords1, coords2):
temp = matrix[coords1[0]][coords1[1]]
matrix[coords1[0]][coords1[1]] = matrix[coords2[0]][coords2[1]]
matrix[coords2[0]][coords2[1]] = temp
Problem Solution In Java
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length, half = matrix.length/2, columnStart = 0;
for (int row=0; row<half; row++) {
for (int column=columnStart; column<n-1; column++) {
rotateE(matrix, row, column);
}
n--;
columnStart++;
}
}
public void rotateE(int[][] matrix, int row, int column) {
int n = matrix.length-1;
int tmp1 = matrix[n-column][row], tmp2 = matrix[row][column], tmp3 = matrix[column][n-row], tmp4 = matrix[n-row][n-column];
matrix[row][column] = tmp1;
matrix[column][n-row] = tmp2;
matrix[n-row][n-column] = tmp3;
matrix[n-column][row] = tmp4;
}
}
Problem Solution In C++
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int s = matrix.size();
int temp;
for (int i = 0; i < s; i++){
for (int j = 0; j < i; j++){
temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for (int i = 0; i < s; i++)
reverse(matrix[i].begin(), matrix[i].end());
}
};
Problem Solution In C
void rotate(int** matrix, int matrixRowSize, int matrixColSize) {
int begin = 0, end = matrixRowSize - 1;
int tmp;
int i;
while(end > begin) {
for(i = begin; i < end; ++i) {
tmp = matrix[begin][i];
matrix[begin][i] = matrix[end - i + begin][begin];
matrix[end - i + begin][begin] = matrix[end][end - i + begin];
matrix[end][end - i + begin] = matrix[i][end];
matrix[i][end] = tmp;
}
++begin;
--end;
}
}