0048 Rotate Image

0048 Rotate Image#

Problem#

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.

Examples#

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

Analysis#

  • Clockwise Rotation \(90 \degree\):

    • swap elements along the left diagnoal

    • reverse elements column by column

  • Clockwise Rotation \(180\degree\):

    • reverse each row

    • reverse eacg column

  • Clockwise Rotation \(270\degree\)

    • swap elements along the right diagonal

    • reverse each column

Solution#

def rotate90(image):
    # swap along left diagnoal
    n = len(image)
    if n == 1:
        return image

    # row-wise
    for i in range(n):
        # column-wise
        for j in range(n-1-i):
            image[i][j], image[n-1-j][n-1-i] = image[n-1-j][n-1-i], image[i][j]
    
    # reverse each column
    for c in range(n):
        u, l = 0, n - 1
        while u <= l:
            image[u][c], image[l][c] = image[l][c], image[u][c]
            u += 1
            l -= 1

    return image

# test
image = [[1,2,3],[4,5,6],[7,8,9]]
print(rotate90(image))

image = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
print(rotate90(image))

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