Notebook

48. Rotate Image

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]]

Example 3:

Input: matrix = [[1]]
Output: [[1]]

Example 4:

Input: matrix = [[1,2],[3,4]]
Output: [[3,1],[4,2]]

Constraints:

matrix.length == n
matrix[i].length == n
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

Source

Code

In [2]:

def rotate(matrix):
    """
    check link image to remember the trick.
    https://javabypatel.blogspot.com/2016/11/rotate-matrix-by-90-degrees-inplace.html
    """
    n = len(matrix) - 1
    for i in range((n + 1) // 2):
        for j in range(i, n - i):
            temp = matrix[i][j]    # no need for temp when doing using one liner
            matrix[i][j] = matrix[n - j][i]
            matrix[n - j][i] = matrix[n - i][n - j]
            matrix[n - i][n - j] = matrix[j][n - i]
            matrix[j][n - i] = temp

In [1]:

def rotate(matrix):
    """Same as above but using the '~' operator:  ~x = -x-1
    [ 0,  1, 2, 3, 4, 5, 6, 7, 8, 9]
     -10 -9 -8 -7 -6 -5 -4 -3 -2 -1  --> negative indexing

    [ 0,  1, 2, 3, 4, 5, 6, 7, 8, 9]
     ~9  ~8 ~7 ~6 ~5 ~4 ~3 ~2 ~1 ~0  --> tilde indexing
    """
    m = len(matrix)
    for i in range(m // 2):
        for j in range((m + 1) // 2):
            temp = matrix[i][j]
            matrix[i][j] = matrix[~j][i]
            matrix[~j][i] = matrix[~i][~j]
            matrix[~i][~j] = matrix[j][~i]
            matrix[j][~i] = temp

In [ ]:

def rotate(matrix):
    """Using reverse and then transpose manually the matrix

        [[0,0,0,0,0],                [[4,4,4,4,4],
         [1,1,1,1,1],   a.reverse()   [3,3,3,3,3],
    a =  [2,2,2,2,2],       ==>       [2,2,2,2,2],
         [3,3,3,3,3],                 [1,1,1,1,1],
         [4,4,4,4,4]]                 [0,0,0,0,0]]
    """
    matrix.reverse()
    for i, _ in enumerate(matrix):
        for j in range(i):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

In [ ]:

def rotate(matrix):
    """Same as above but transpose using zip(*) (much faster)

        [[0,0,0,0,0],                [[0,1,2,3,4],
         [1,1,1,1,1],     zip(*a)     [0,1,2,3,4],
    a =  [2,2,2,2,2],       ==>       [0,1,2,3,4],
         [3,3,3,3,3],                 [0,1,2,3,4],
         [4,4,4,4,4]]                 [0,1,2,3,4]]

    Note: zip returns tuples --> requires conversion into lists

    BUT: zip() create additional space to hold and return the result matrix.
    so technically, it's not a 0(1) memory solution
    """
    matrix.reverse()
    matrix[:] = map(list, zip(*matrix))
    
    #          A[:] =       vs         A =
    #       replace in              makes a 
    #     original list        refence to object

Check

In [23]:

matrix = [[1,2,3],[4,5,6],[7,8,9]]
rotate(matrix)

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

In [ ]:

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

In [ ]:

matrix = [[1,2],[3,4]]
rotate(matrix)

In [ ]:

matrix = [[1]]]
rotate(matrix)