LeetCode 48.Rotate Image

Intuition

swap across line y = -x swap across y axis. For example

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

Optimal Solution

Thinking and coding this in the spot can be difficult and the idea is not very intuitive so I think I will stick with NeetCode's solution

which is swap by layer and then go into inner layer the logic is to swap the four corners and then move the pointer and swap the four corners again r-l times because for a matrix with length 4 if we swap four corners and move pointer we move the pointer 2 times.

and after r-l times we move the pointer to the inner layer by r -=1 and l += 1 top = l bottom = r

Also another trick to be aware of is to put top left in the temp first and then assign bottom left to top left bottom right to bottom left top right to bottom right and top left to top right

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        l,r = 0, len(matrix) -1

        while l < r:
            for i in range(r-l):
                top, bottom = l, r

                top_left = matrix[top][l + i]
                matrix[top][l+i] = matrix[bottom - i][l]
                matrix[bottom - i][l] = matrix[bottom][r - i]
                matrix[bottom][r - i] = matrix[top + i][r]
                matrix[top + i][r] = top_left

            r -= 1
            l += 1

Time Complexity

O(n^2) time complexity O(1) space complexity