Teaching Kids Programming – Rotate a 2D Matrix/Image 90 Degree Clockwise

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Algorithm to Rotate a 2D Matrix/Image 90 Degree Clockwise

We can first transpose the matrix, and then reverse each row – this will be virtually rotating a matrix 90 degree in two passes.

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        def transpose(A):
            R, C = len(A), len(A[0])
            T = [[None] * R for _ in range(C)]
            for r in range(R):
                for c in range(C):
                    T[c][r] = A[r][c]
            return T       
        
        matrix[:] = transpose(matrix)
        for r in range(len(matrix)):
            matrix[r] = matrix[r][::-1]

The time complexity is O(RC) where R are C are the number of rows and columns of the matrix/image respectively. The space complexity is O(RC) as we are allocating a new matrix for return.

If it is N*N, we can rotate this in place:

class Solution:    
    def rotate(self, matrix: List[List[int]]) -> None:
        if not matrix:
            return
        rows = len(matrix)
        cols = len(matrix[0])
        for r in range(rows):
            for c in range(r):
                matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
                
        for r in range(rows):
            for c in range(cols//2):
                matrix[r][c], matrix[r][cols - c - 1] = matrix[r][cols - c - 1], matrix[r][c]           

Time complexity O(RC), space complexity O(1).

See also: How to Rotate a Matrix (Clockwise and Anti-clockwise) in place?

We can perform the Anti-Clockwise rotations three times to get a clockwise rotation or vice versa: Teaching Kids Programming – Rotate a 2D Matrix/Image 90 Degree Anti-Clockwise

–EOF (The Ultimate Computing & Technology Blog) —