KeiruaProd

I help my clients acquire new users and make more money with their web businesses. I have ten years of experience with SaaS projects. If that’s something you need help with, we should get in touch!
< Back to article list

It’s not that trivial to rotate a N*N matrix 90° clockwise

I came upon a coding exercise recently. My reaction to the first part was “meh, that’s easy”. For the second part, was “ok, wait a second”.

Turns out it’s a great way to learn how to think through an algorithm and improve it.

Here is the 2-part question:

Give it a try ! Let’s say we have a matrix m, we want to turn it into r:

# N = 3, m is a 3x3 matrix
m = [[1, 2, 3],
     [4, 5, 6],
     [7, 8, 9]]
# What we want to achieve after the 90°CW rotation:
r = [[7, 4, 1],
     [8, 5, 2],
     [9, 6, 3]]

Boilerplate

In order to run the code here, we first need some boilerplate to create and print some matrices:

def create_incremental_matrix(N):
    """
    Create a N*N matrix of the form:
    [[1,2,3],
    [4,5,6],
    [7,8,9]]
    """
    return [[y * N + x for x in range(N)] for y in range(N)]

def printmatrix(matrix):
    """pretty prints the matrix so that large values are still readable"""
    # we are looking for the largest size of number, which is the size of the largest number
    max_v = max(v for line in matrix for v in line)
    max_w = len(str(max_v))
    for line in matrix:
        print(" ".join(str(i).center(1 + max_w) for i in line))

Rotating a matrix 90°

The first thing to note is that each coordinate gets mapped to a new coordinate. If we can write any value to another matrix with the same coordinates, we are done.

def rotatem(matrix):
    """rotate the matrix 90°CW by moving the entries to their new coordinates"""
    w = len(matrix)
    # the second matrix we need
    # time complexity: O(N^2)
    out = [[0 for _ in range(w)] for _ in range(w)]
    # time complexity: O(N^2) 
    for y in range(w):
        for x in range(w):
        	# Clockwise rotation
			# (x, y) becomes (x, N-y-1)
			# Counter-clockwise rotation
			# (x, y) becomes (N-x-1, N-y-1)
            out[x][w - y - 1] = matrix[y][x]
    return out

What is the complexity of this algorithm ?

Our actual goal is not simply to drop the extra memory requirement : we want at least an O(N^2) algorithm.

Doing it in place

I’ve found two different ways to approach the problem.

Using cycles in order to perform multiple swaps at once

Doing the rotation in place means that we need to come up with a way to perform many swaps at once: (x, y) becomes (x, N-y-1), (x, N-y-1) goes somewhere else… how many times? Only four:

Lets take an another example, with only one (visible) cycle:

[0, 1, 0, 0]    [0, 4, 0, 0]
[0, 0, 0, 2] -> [0, 0, 0, 1] 
[4, 0, 0, 0]    [3, 0, 0, 0]
[0, 0, 3, 0]    [0, 0, 2, 0]

Generalizing to any coordinate is quite tricky to write, because finding the target coordinates of each element of the cycle is error-prone. I took a piece of paper, wrote some examples (I found N=3 not to be clear, N=5 worked well for me), then found a formula:

We also need to find all the cycles that need to be rotated:

def rotate_with_cycles_in_place(matrix):
    """rotate a matrix 90°CW by using cycles"""
    w = len(matrix)
    # So the idea here is that there are 4-cycles (cycles of length 4).
    # Inside any 4 cycle, we can perform the rotation in place
    # by using a temporary variable to swap them
    # Then, we will loop through all 4-cycles in order to swap them all
    for x in range(w // 2):
        for y in range(x, w - x - 1):
            # rotate a 4-cycle clockwise
            tmp = matrix[y][x]
            matrix[y][x] = matrix[w - x - 1][y]
            matrix[w - x - 1][y] = matrix[w - y - 1][w - x - 1]
            matrix[w - y - 1][w - x - 1] = matrix[x][w - y - 1]
            matrix[x][w - y - 1] = tmp
    # If we want rotate counter-clockwise, we reverse the order of the operations
    # tmp = matrix[y][x]
    # matrix[y][x] = matrix[x][w-y-1]
    # matrix[x][w-y-1] = matrix[w-y-1][w-x-1]
    # matrix[w-y-1][w-x-1] = matrix[w-x-1][y]
    # matrix[w - x - 1][y] = tmp
    return matrix

The time complexity is O(N/2 * N/2) = O(N^2/4) = O(N^2), because:

Using matrix transposition

That was quite complicated. I’ve found a slightly different approach using matrix transposition.

The idea is that a 90°CW rotation is a transposition (inversing rows and colums) then the reversal of all the columns:

 start    -> transpose -> reverse columns
[1, 2, 3]    [1, 4, 7]    [7, 4, 1]
[4, 5, 6] -> [2, 5, 8] -> [8, 5, 2] 
[7, 8, 9]    [3, 6, 9]    [9, 6, 3]

What about complexity ?

def rotate_in_place_transpose_reverse_cols(matrix):
    """rotate the matrix 90°CW in place by transposing then reversing the colums the matrix"""
    w = len(matrix)
    # First we transpose
    # (m[y][x] -> m[x][y], we have to take care not to do that twice!)
    # Complexity: O(N*N/2)
    for y in range(w):
        for x in range(y, w):
            tmp = matrix[y][x]
            matrix[y][x] = matrix[x][y]
            matrix[x][y] = tmp

    # then we reverse the columns
    # we swap half the rows in every line
    # Complexity: O(N*N/2) too
    for y in range(w):
        for x in range(0, w // 2):
            tmp = matrix[y][x]
            matrix[y][x] = matrix[y][w - x - 1]
            matrix[y][w - x - 1] = tmp

    return matrix

Conclusion