Practice Algorithms with Math Puzzles Part 3 Matrix Rotation

Hello, In this part I will explain in-place rotation of a 2D matrix, without using another matrix for storing, so that we just change the original matrix.

Photo by Karla Hernandez on Unsplash

I will explain the case when the degree of rotation is 90 degrees as a ground case and then talk about other cases like -90, 180, 270.

image 1

As you can see we are dealing with 2 squares, orange and green. We should come up with a way to turn left orange square into right one. The following algorithm does this for each square in-place.

If we want to do it in-place then our matrix should be squared obviously.

The number of squares is half of the matrix size.

def rotate_matrix(M):
    N=len(M)
    # Loop through all squares
    for i in range(0, int(N / 2)):
        # Consider elements in group of 4 in current square
        for j in range(x, N-i-1):
            temp = M[i][j]
            M[i][j] = M[N - 1 - j][i]
            M[N - 1 - j][i] = M[N - 1 - i][N - 1 - j]
            M[N - 1 - i][N - 1 - j] = M[j][N - 1 - i]
            M[j][N - 1 - i] = temp

Here I have drawn what happens inside algorithm for a 3 by 3 matrix for better understanding.

image 2

Pay attention that due to the way we are indexing the matrix to access elements we can achieve each step in image 2.

The cases of -90 and 270 degrees rotation would be the same. We use a similar algorithm to 90 degrees case for -90 degrees case:

image 3

The way we replace elements by each other in each group of four in each square is reversed of the way we did it for 90 degrees and this reflects in our indexing in the inner loop.

def rotate_matrix(M):
    N=len(M)
    # loop through all squares    
    for i in range(N // 2):
        # Consider elements in group of 4 in current square
        for j in range(i, N-i-1):
            # store current cell in temp variable
            temp = M[i][j]
            # move value from right to top
            M[i][j] = M[j][N-1-j]
            # move value from bottom to right
            M[j][N-1-i] = M[N-1-i][N-1-j]
            # move value from left to bottom
            M[N-1-i][N-1-j] = M[N-1-j][i]
            # assign temp to left
            M[N-1-j][i] = temp

For the case of 180 degrees rotation we swap elements of the first row with last row in reverse order and so on. For an odd size matrix when we reach to middle row we just reverse it.

image 4

def rotate_matrix(M):
    N = len(M)
    for i in range(N // 2):
        for j in range(N):
            temp = M[i][j]
            M[i][j] = M[N - i - 1][N - j - 1]
            M[N - i - 1][N - j - 1] = temp
    # the case when the matrix has odd dimensions
    if N % 2 == 1:
        for j in range(N // 2):
            temp = M[N // 2][j]
            M[N // 2][j] = M[N // 2][N - j - 1]
            M[N // 2][N - j - 1] = temp

Thanks for reading.