# 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).

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]
]

Could you do this in-place?

@tag-array


# 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


# Code

Java

another way: reference https://leetcode.com/problems/rotate-image/solution/

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]
]


java implementation

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;
}
}
}
}