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]]
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))
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 ?
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.
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:
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:
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 ?
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