Leetcode 48: Rotate Image

Code

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """Do not return anything, modify matrix in-place instead."""
        
        assert matrix is not None, "Matrix is None!"
    
        for row in matrix:
            for i in range(len(row) // 2):
                temp = row[i]
                row[i] = row[len(row) - 1 - i]
                row[len(row) - 1 - i] = temp
    
    
        for k in range(len(matrix)):
            for i in range(len(matrix[k]) - 1 - k):
                temp = matrix[k][i]
                matrix[k][i] = matrix[len(matrix) - 1 - i][len(matrix) - 1 - k]
                matrix[len(matrix) - 1 - i][len(matrix) - 1 - k] = temp

First step: Pre-process each row

Each index swaps with the corresponding index at the end of the row. That is:

[0] swaps with [len(row) - 1], [1] swaps with [len(row) - 1 - 1], etc.

len(row) // 2 in the code means we only need to swap half-length amount of time, any more swaps will swap back to the original order.

An example:

1   2   3        3  2  1
4   5   6   ->   6  5  4
7   8   9        9  8  7

Second step: Swap bits diagonally

Imagine the matrix is composed of multiple sub-matrices, swap each diagonal corner pair (top-left with corresponding bottom-right) that the top-left bit in the pair is LESS than len(matrix) - 1 - k where k represents the row ID. That is, if you notice the diagonal line starting from top-right to left-bottom, which is a line of bits that are already in their positions by the pre-process (Think about how the rotate works). And then we just need to swap each one counter diagonally once, therefore only swap the bits LESS than the bit in the diagonal line. In the below implementation, k represents the row ID, i represents the column ID in that row.

An example:

3  2  1                     7   2   1                    7   4   1                    7   4   1 
6  5  4   -> 1st k, 1st i:  6   5   4  -> 1st k, 2nd i:  6   5   2  -> 2nd k, 1st i:  8   5   2
9  8  7                     9   8   3                    9   8   3                    9   6   3