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.

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

What about complexity ?

- 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 ;)

See a typo ? You can suggest a modification on Github.