[Top Interview 150] 48. Rotate Image

Solution)

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

	# Initialization of boundaries
        left, right = 0, len(matrix)-1

	# Select the boundary
        while left < right:
        # Rotate the numbers in the boundary
            for i in range(right-left):
                top, bottom = left, right

                temp = matrix[top][left + i]

                matrix[top][left+i] = matrix[bottom-i][left]

                matrix[bottom-i][left] = matrix[bottom][right-i]

                matrix[bottom][right-i] = matrix[top+i][right]

                matrix[top+i][right] = temp


            left += 1
            right -= 1

 
 
Problem: LeetCode
Reference: NeetCode
 
Time Complexity: O(n^2)
Space Complexity: O(1)
 
 

Explanation)

There will be one while-loop and one nested for-loop.
 
While-loop indicates which boundary of numbers we're rotating.
 
 

 
 
For-loop indicates which number within the selected boundary we're rotating.
 
 

 
 
You probably already know the logic/order of rotation, but understanding how to code that logic using the two loops is very important.
 
 

Initialization)

Similar to the last problem, you need variables that indicate the boundaries.
 
However, this time the matrix is a square matrix, thus top has the same value as left. Also, bottom has the same value as right. So we'll set those values later. 
 

def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """

        left, right = 0, len(matrix)-1

 
 

Two loops)

Again, be aware of the meanings that the loops indicate.
 
while-loop indicates the boundaries and for-loop indicates the numbers in the selected boundary.
Even if this doesn't make sense right now, just have that in mind and keep looking at the codes below.
 
And because matrix is a square matrix, top and bottom have the same values as left and right.
 

def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """

        left, right = 0, len(matrix)-1

        while left < right:
            for i in range(right-left):
                top, bottom = left, right

 
 

Logic of rotation)

Below is the order of our rotation.
 
 

Order of the rotation

1) Save topleft value to temp
2) botleft value -> topleft
3) botright value -> botleft
4) topright value -> botright
5) topleft(temp) value ->topright
 
 
We set the order as above because this is the most efficient way of utilizing one temp variable while rotating four values.
 
We repeat this until the for-loop is completed (until all the numbers in the selected boundary is rotated).
 
If all the numbers are rotated, then we update left/right and move on to the next while loop (then we look at the next inner boundary and rotate the numbers again).
 

def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """

        # Initialization

        while left < right:
            for i in range(right-left):
                top, bottom = left, right

                temp = matrix[top][left + i]

                matrix[top][left+i] = matrix[bottom-i][left]
                
                matrix[bottom-i][left] = matrix[bottom][right-i]

                matrix[bottom][right-i] = matrix[top+i][right]

                matrix[top+i][right] = temp


            left += 1
            right -= 1

 
 
 
I thought of a similar logic but couldn't code it the way I wanted to. I think I'm starting to get the hang of how to solve matrix problems though.