# 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:

• Can you write a function that rotates a N*N matrix 90 clockwise?
• Can you do it in-place?

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 ?

• time: `2*O(N^2)`, so `O(N^2)`
• memory: `2*N^2`, because we need to store the initial matrix as well as the output.

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:

• The upper-left corner goes to the upper-right corner
• the upper-right corner goes to the bottom-right corner
• the bottom-right corner goes to the bottom-left corner
• bottom-left corner goes to the upper-left corner

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:

• (x,y) becomes (y, w - x - 1)
• (y, w - x - 1) becomes (w - x - 1, w - y - 1)
• (w - x - 1,w - y - 1) becomes (w - y - 1, x)
• (w - y - 1, x) becomes (x,y)

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:

• the x loop is `O(N/2)`
• the y loop goes from x to w-x-1, which is N/2 on average
• the 4-cycle swap is `O(1)`
• constants do not matter in big-O complexity

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

• transposition can be done in place in `O(N/2)`
• same for reversal The time complexity is then twice `O(N*N/2)`, so `O(N^2)`, so our goal is met too.
``````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

• Pen and paper are great tools to come up with solutions and ideas
• I’m not that rusty with coding exercises ;)
• Complexity analysis is a great tool to compare solutions
• The real world needs far more than complexity analysis ;)