48.Rotate_Image(Medium).md

48. Rotate Image (Medium)

Date and Time: Jul 14, 2024, 16:52 (EST)

Link: https://leetcode.com/problems/rotate-image/

Question:

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.

Example 1:

Input: matrix = [ [1, 2, 3], [4,5,6], [7,8,9] ]

Output: [ [7,4,1], [8,5,2], [9,6,3] ]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]

Output: [ [15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11] ]

Constraints:

• n == matrix.length == matrix[i].length

• 1 <= n <= 20

• -1000 <= matrix[i][j] <= 1000

KeyPoints:

We can use l, r, t, b for the boundaries, then we can start rotating the four corners of the matrix, we can first store the top-left to tmp then we move the bottom-left -> top-left, we repeat this process for bottom-right -> bottom-left, top-right -> bottom-right, and finally tmp -> top-right.

After that, we use a while loop to continue other entries on the outer boundaries, look at Example 2, for i in range(r - l) can let us move the other entries on the same boundaries. Next, we can update l, r to move from the outer boundaries to inner boundaries.

To better understand range(r - l), in Example 2 when the square is width 4, r - l = 3, so we only incremenet to rotate the other two entries on the boundary. After i += 1, r -= 1, we are now in the inner square of width 2, and r - l = 1, which we don't need to rotate other entry on the boundary, which is correct.

My Solution:

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # Use four ptrs to rotate
        l, r = 0, len(matrix) - 1
        while l < r:
            t, b = l, r
            for i in range(r - l):
                tmp = matrix[t][l + i]  # first element in matrix
                matrix[t][l + i] = matrix[b - i][l]
                matrix[b - i][l] = matrix[b][r - i]
                matrix[b][r - i] = matrix[t + i][r]
                matrix[t + i][r] = tmp
            # Going to next level
            l += 1
            r -= 1

Time Complexity: $O(m * n)$
Space Complexity: $O(1)$