48. Rotate Image

Description:

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.

'''
[1] reverse row-by-line and transpose

idea::
reverse row-by-line and transpose

code::
def rotate(self, matrix: List[List[int]]) -> None:
    self.reverse(matrix)
    self.transpose(matrix)

def reverse(self, matrix):
    top,bottom=0,len(matrix)-1

    while top<bottom:
        matrix[top],matrix[bottom]=matrix[bottom],matrix[top]
        top+=1
        bottom-=1

def transpose(self,matrix):
    for i in range(len(matrix)):
        for j in range(i+1,len(matrix[0])):
            matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
-T/C: O(m+n)
-S/C: O(1)
'''
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        self.reverse(matrix)
        self.transpose(matrix)
        
    def reverse(self, matrix):
        top,bottom=0,len(matrix)-1
        
        while top<bottom:
            matrix[top],matrix[bottom]=matrix[bottom],matrix[top]
            top+=1
            bottom-=1
    
    def transpose(self,matrix):
        for i in range(len(matrix)):
            for j in range(i+1,len(matrix[0])):
                matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]