General idea
Rotate image is essentially rotating each outer layer by 90 degrees until we reached the inner-most layer.(for odd size matrix, that’s the single number in the middle, for even size matrix, that is the matrix with length 2 in the middle).
How many layers needed to rotate
For a matrix with length n, there will be n // 2 layers.
Rotate
Example
a b c g d a
d e f -> h e b
g h i i f c
Rotating groups
In each layer, we have 4 groups that need to swap. Each group will have size (layer_len – 1). So for our example above, the outerlayer has size 3 so the group size is 2. They are [a,b], [c,f], [i,h], [g,d].
And each group swap with the next group in a clock-wise fashion.
We also notice that, the first group will always starts on matrix[j][j] and moves in horizontal fashion.
The second group will always start on matrix[j][j + group_size] and moves horizontally.
class Solution:
def rotate(self, matrix: 'List[List[int]]') -> 'None':
"""
Do not return anything, modify matrix in-place instead.
Basically, we want to transpose the matrix.
A_{ij} = A_{ji}}
"""
size_group = len(matrix) - 1
for i in range(len(matrix)//2):
pos = 0
for j in range(size_group):
temp = [matrix[i][i + pos],
matrix[i + pos][i + size_group],
matrix[i + size_group][i + size_group - pos],
matrix[i + size_group - pos][i]
]
matrix[i][i + pos] = temp[3]
matrix[i + pos][i + size_group] = temp[0]
matrix[i + size_group][i + size_group - pos]= temp[1]
matrix[i + size_group - pos][i] = temp[2]
pos += 1
size_group -= 2