Devin's Blog

Rotate Image

4 min read

TARGET DECK: Leetcode FILE TAGS: Medium

Intuition

  • Take transpose, then rotate 90 degrees.
  • To take the transpose, notice that (i, j) = (j, i) when i j
  • Alternatively, you may “rotate one cell at a time”. However, notice that you cannot simply rotate any cell in any way.
  • That is to say: You need to convert those cells farthest away from each other, since otherwise there will be a conflict in which the cells you rotate are conflicting, and override each other.
  • Therefore, we rotate furthest away, and to do that, we pay very close attention to the boundaries, keeping a variable for top, down, left, and right respectively, wherein:
    • top left moves right, and replaces right.
    • top right moves down, and replaces down.
    • bottom right moves left, and replaces left.
    • bottom left moves up, and replaces up.
  • To understand why, visualize a Rubiks Cube falling to the side, and notice the rotations.

Complexity

Runtime

since each row and column is traversed (otherwise called where M is the number of cells since each cell is traversed).

Space

Code

Setting Identical Pointers

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        bottom, top = len(matrix) - 1, 0
        left, right = 0, len(matrix) - 1
        while left < right: # Create sub problem square
            bottom, top = right, left
            for i in range(right - left): # Go only within the bounds of the square subproblem
                topleft = matrix[top][left + i] # Top left is going right
                topright = matrix[top + i][right] # Top right is going down
                bottomright = matrix[bottom][right - i] # Bottom right is going left
                bottomleft = matrix[bottom - i][left] # Bottom left is going up
 
                matrix[top + i][right] = topleft # topright = topleft
                matrix[bottom][right - i]= topright # bottomright = topright
                matrix[bottom - i][left] = bottomright # bottomleft = bottomright
                matrix[top][left + i] = bottomleft # topleft = bottomleft
 
            left += 1
            right -= 1
  • This implies that top and bottom is syntactic sugar, but that would be quite confusing and less readable:
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        left, right = 0, len(matrix) - 1
        while left < right: # Create sub problem square
            right, left = right, left
            for i in range(right - left): # Go only within the bounds of the square subproblem
                topleft = matrix[left][left + i] # Top left is going right
                topright = matrix[left + i][right] # Top right is going down
                bottomright = matrix[right][right - i] # Bottom right is going left
                bottomleft = matrix[right - i][left] # Bottom left is going up
 
                matrix[left + i][right] = topleft # topright = topleft
                matrix[right][right - i]= topright # bottomright = topright
                matrix[right - i][left] = bottomright # bottomleft = bottomright
                matrix[left][left + i] = bottomleft # topleft = bottomleft
 
            left += 1
            right -= 1

Rotating One Cell at a Time

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        bottom, top = len(matrix) - 1, 0
        left, right = 0, len(matrix) - 1
        while left < right: # Create sub problem square
            for i in range(right - left): # Go only within the bounds of the square subproblem
                topleft = matrix[top][left + i] # Top left is going right
                topright = matrix[top + i][right] # Top right is going down
                bottomright = matrix[bottom][right - i] # Bottom right is going left
                bottomleft = matrix[bottom - i][left] # Bottom left is going up
 
                matrix[top + i][right] = topleft # topright = topleft
                matrix[bottom][right - i]= topright # bottomright = topright
                matrix[bottom - i][left] = bottomright # bottomleft = bottomright
                matrix[top][left + i] = bottomleft # topleft = bottomleft
 
            left += 1
            right -= 1
            top += 1
            bottom -= 1

Transpose then Flipping Columns

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
    
        n = len(matrix)
        def transpose():
            for r in range(n):
                for c in range(n):
                    if r <= c:
                        matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
        
        def flipcols():
            for c in range(n // 2): # [0, n / 2)
                for r in range(n):
                    matrix[r][c], matrix[r][n - c - 1] =  matrix[r][n - c - 1], matrix[r][c]
 
        transpose()
        flipcols()

Notes

Cards

START Basic Front: Rotate Image Back: Use Transpose, then flip the columns. Alternatively, rotate all the cells that are furthest away from each other.

END

References

Graph View