# Question

Formatted question description: https://leetcode.ca/all/48.html

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.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]


Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]


Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

# Algorithm

Use a simple example to analyze:

1 2 3　　　 　　 7 4 1

4 5 6　　-->　　 8 5 2

7 8 9 　　　 　　 9 6 3


There are many ways to flip 90 degrees, one or more steps can be solved, first look at a direct method, this method is to cover the previous numbers in a clockwise order, starting from the four top corners, and then To traverse in the middle, the coordinates covered each time are the same, as follows:

(i, j) <- (n-1-j, i) <- (n-1-i, n-1-j) <- (j, n-1-i)

This is actually a cyclic process. The first position covers the fourth position, where the value range of i is [0, n/2), and the value range of j is [i, n-1-i), As for why i and j are in this value range, why i don’t need to traverse [n/2, n). If you carefully observe the relationship between these positions, it is not difficult to find that the range of column j is actually [i, n-1 -i) Turn 90 degrees clockwise, which is exactly the position of [n/2, n) in row i. This method changes four numbers each time through the loop

### Note

I missed a key concept, I DO NOT have to rotate all numbers on one edge from start to end

1. for corner positions of each layer, rotate first is also changing end of that layer row
2. for numbers not corner, rotate them

eg:
1 2
3 4

one rotate is enough, since except corner position, no other positions

eg:
1   2   3   4   5
6   7   8   9   10
11  12  13  14  15
16  17  18  19  20
21  22  23  24  25

like in row "1,2,3,4,5", rotate 1 will also change 5
so, for each edge, rotate to the penultimate one, that is, only rotate "1,2,3,4" is enough, and 5 will be processed in the next operation


## another way: transpose + reflect

original

[
[1,2,3],
[4,5,6],
[7,8,9]
]


diagonal as reverse base line

[
[1,4,7],
[2,5,8],
[3,6,9]
]


every row, to reverse from left to right

[
[7,4,1],
[8,5,2],
[9,6,3]
]


# Code

• 

public class Rotate_Image {

public class Solution {
/*  eg:

1   2   3   4   5
6   7   8   9   10
11  12  13  14  15
16  17  18  19  20
21  22  23  24  25
*/

public void rotate(int[][] m) { // m for matrix

if (m == null || m.length == 0) {
return;
}

// for each circle, start position is (i,i), length is rectangle size
// eg. above: (0,0), length=5; (1,1), length=3
int i = 0;
int length = m.length;

while (i < m.length / 2) {

int count = 0;
while (count < length - 1) { // @note: extra attention here "-1".
// while (count < length) {

int tmp = m[i][i + count];

// i+length-1: last index of this rectangle
// i+length-1 - count: index from backward
m[i][i + count] = m[i + length - 1 - count][i];
m[i + length - 1 - count][i] = m[i + length - 1][i + length - 1 - count];
m[i + length - 1][i + length - 1 - count] = m[i + count][i + length - 1];
m[i + count][i + length - 1] = tmp;

count++;
}

length -= 2; // @note: shrink each edge length by 2
i++; // start point moving along diagonal
}
}
}

// An Inplace function to rotate a N x N matrix by 90 degrees in anti-clockwise direction
static void rotateMatrix_anticlock(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;
}
}
}

static void rotateMatrix_clockwise(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;
}
}
}
}

//////

class Solution_diagonal {
public void rotate(int[][] matrix) {
transpose(matrix);
reflect(matrix);
}

public void transpose(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int tmp = matrix[j][i];
matrix[j][i] = matrix[i][j];
matrix[i][j] = tmp;
}
}
}

public void reflect(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][n - j - 1];
matrix[i][n - j - 1] = tmp;
}
}
}
}

//////

class Solution {
public void rotate(int[][] matrix) {
int s = 0, n = matrix.length;
while (s < (n >> 1)) {
int e = n - s - 1;
for (int i = s; i < e; ++i) {
int t = matrix[i][e];
matrix[i][e] = matrix[s][i];
matrix[s][i] = matrix[n - i - 1][s];
matrix[n - i - 1][s] = matrix[e][n - i - 1];
matrix[e][n - i - 1] = t;
}
++s;
}
}
}

• // OJ: https://leetcode.com/problems/rotate-image/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
void rotate(vector<vector<int>>& A) {
int N = A.size();
for (int i = 0; i < N / 2; ++i) {
for (int j = i; j < N - i - 1; ++j) {
int tmp = A[i][j];
A[i][j] = A[N - j - 1][i];
A[N - j - 1][i] = A[N - i - 1][N - j - 1];
A[N - i - 1][N - j - 1] = A[j][N - i - 1];
A[j][N - i - 1] = tmp;
}
}
}
};

• class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
if len(matrix) == 0:
return
h = len(matrix)
w = len(matrix[0])
for i in range(0, h): # mirror
for j in range(0, w / 2):
matrix[i][j], matrix[i][w - j - 1] = matrix[i][w - j - 1], matrix[i][j]

for i in range(0, h): # transpos
for j in range(0, w - 1 - i):
matrix[i][j], matrix[w - 1 - j][h - 1 - i] = matrix[w - 1 - j][h - 1 - i], matrix[i][j]

############

class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
for i in range(n >> 1):
for j in range(n):
matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]
for i in range(n):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]


• func rotate(matrix [][]int) {
n := len(matrix)
// matrix transpose
for i := 0; i < n; i++ {
for j := i; j < n; j++ {
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
}
}
// reverse each matrix[i]
for i := 0; i < n; i++ {
for j, k := 0, n-1; j < k; j, k = j+1, k-1 {
matrix[i][j], matrix[i][k] = matrix[i][k], matrix[i][j]
}
}
}

• /**
Do not return anything, modify matrix in-place instead.
*/
function rotate(matrix: number[][]): void {
let n = matrix[0].length;
for (let i = 0; i < Math.floor(n / 2); i++) {
for (let j = 0; j < Math.floor((n + 1) / 2); j++) {
let tmp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = tmp;
}
}
}


• /**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function (matrix) {
matrix.reverse();
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < i; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
};


• impl Solution {
pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
let n = matrix.len();
for i in 0..n / 2 {
for j in i..n - i - 1 {
let t = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = t;
}
}
}
}


• public class Solution {
public void Rotate(int[][] matrix) {
int n = matrix.Length;
for (int i = 0; i < n >> 1; ++i) {
for (int j = 0; j < n; ++j) {
int t = matrix[i][j];
matrix[i][j] = matrix[n - i - 1][j];
matrix[n - i - 1][j] = t;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
int t = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = t;
}
}
}
}