Rotation Matrix

Next up is “Rotate Matrix” which, unsurprisingly, rotates an X by X matrix by 90 degrees. There are two ways of tackling this problem, the first which is creating a new matrix and copying over each of the cells, and the second is to be able to swap elements in place. The second is harder because it means you have to iterate around the matrix with each of the values because you don’t have a separate space to put them.

Let’s go over the solution which copies elements to a new matrix:

def rotateMatrix(mtrx):
    N = len(mtrx)
    newMtrx = [[0 for x in range(N)] for y in range(N)]
    for r in range(N):
        for c in range(N):
            newMtrx[r][c] = mtrx[N-1-c][r]
    return newMtrx

and let’s say we have a 4x4 matrix which looks like:

[['A','B','C','D'],
 ['E','F','G','H'],
 ['I','J','K','L'],
 ['M','N','O','P']]

We want to rotate that matrix so that it looks like:

[['M','I','E','A'],
 ['N','J','F','B'],
 ['O','K','G','C'],
 ['P','L','H','D']]

In rotateMatrix() we create a new blank 4x4 matrix initially filled with zeros. We then walk through each of the cells of the matrix and take each cell in each column from the bottom up. The runtime here is O(N) even though we have the two for loops because we’re only ever touching each cell once. The biggest problem is that we’re using twice the amount of space because of our new matrix.

Now for the second solution. To rotate without creating a new matrix, we instead will need to carry each cell around the matrix. So in the case of our above matrix, we save the ‘A’ from (0,0) and then carry the ’M’ from (3,0). We then take the ‘P’ from (3,3) and put it in (3,0), and then the ’D’ from (0,3) and put it in (3,3). Repeat that process for ‘B’ and ‘C’, and then rotate the cells at the center of the matrix.

Here’s the code:

def rotateMatrixInPlace(mtrx):
    N = len(mtrx)
    for r in range(N/2):
        for c in range(r, N-1-r):
            tmp = mtrx[r][c]
            mtrx[r][c] = mtrx[N-1-c][r]
            mtrx[N-1-c][r] = mtrx[N-1-r][N-1-c]
            mtrx[N-1-r][N-1-c] = mtrx[c][N-1-r]
            mtrx[c][N-1-r] = tmp

This again works out to O(N) since at most we’re going to 20 swaps (16 for copying around the cells, and 4 for the swaps).