For some reason that I haven’t quite ascertained, matrices scare me. I’ve tried living my life as if they don’t exist, but it hasn’t quite worked. This nagging sensation in the back of my mind tells me that it’s time to put on my big boy pants.
In this post, we’ll be looking at a quite common problem that seems to be featured on all of the coding sites and is in my copy of Cracking the Coding Interview. Simply: rotate a matrix 90° clockwise and do it in-place.
It seems to be marked as an “easy” problem on every site, but I didn’t think it was so easy. The whole ranking thing is mostly bollocks anyway. Everyone learns differently.
Anyway, my eyes glaze over when I encounter a matrix question, and I’ll more often than not skip to another question. And that’s not good. I need to tackle my irrational fear of two-dimensional arrays. And, on a side note, what a completely idiotic thing to fear.
Setup
For the sake of this problem, we’ll only be looking at matrices whose columns and rows have the same length (N x N). For example:
+-------+ | 1 | 2 | |-------| | 3 | 4 | +-------+ +-----------+ | 1 | 2 | 3 | |-----------| | 4 | 5 | 6 | |-----------| | 7 | 8 | 9 | +-----------+ +-------------------+ | 1 | 2 | 3 | 4 | |-------------------| | 5 | 6 | 7 | 8 | |-------------------| | 9 | 10 | 11 | 12 | |-------------------| | 13 | 14 | 15 | 16 | +-------------------+ +------------------------+ | 1 | 2 | 3 | 4 | 5 | |------------------------| | 6 | 7 | 8 | 9 | 10 | |------------------------| | 11 | 12 | 13 | 14 | 15 | |------------------------| | 16 | 17 | 18 | 19 | 20 | |------------------------| | 21 | 22 | 23 | 24 | 25 | +------------------------+
That was just an exercise in self-indulgence.
Let’s take a look at the before and after:
+-----------+ +-----------+
| 1 | 2 | 3 | | 7 | 4 | 1 |
|-----------| |-----------|
| 4 | 5 | 6 | =====> | 8 | 5 | 2 |
|-----------| |-----------|
| 7 | 8 | 9 | | 9 | 6 | 3 |
+-----------+ +-----------+
+-------------------+ +-------------------+
| 1 | 2 | 3 | 4 | | 13 | 9 | 5 | 1 |
|-------------------| |-------------------|
| 5 | 6 | 7 | 8 | | 14 | 10 | 6 | 2 |
|-------------------| =====> |-------------------|
| 9 | 10 | 11 | 12 | | 15 | 11 | 7 | 3 |
|-------------------| |-------------------|
| 13 | 14 | 15 | 16 | | 16 | 12 | 8 | 4 |
+-------------------+ +-------------------+
+------------------------+ +------------------------+
| 1 | 2 | 3 | 4 | 5 | | 21 | 16 | 11 | 6 | 1 |
|------------------------| |------------------------|
| 6 | 7 | 8 | 9 | 10 | | 22 | 17 | 12 | 7 | 2 |
|------------------------| |------------------------|
| 11 | 12 | 13 | 14 | 15 | =====> | 23 | 18 | 13 | 8 | 3 |
|------------------------| |------------------------|
| 16 | 17 | 18 | 19 | 20 | | 24 | 19 | 14 | 9 | 4 |
|------------------------| |------------------------|
| 21 | 22 | 23 | 24 | 25 | | 25 | 20 | 15 | 10 | 5 |
+------------------------+ +------------------------+
Implementation
Here’s a nice function to create an N x N array:
def make_matrix(rows):
matrix = []
row = []
for i in range(1, rows**2 + 1):
row.append(i)
if i % rows == 0:
matrix.append(row)
row = []
return matrix
I’m aware that the
numpypackage has several APIs that can be used to create or operate on a matrix:et al.
I’m sure you can guess my opinion. If you’re unsure about how to implement any of these yourself, don’t use this package or any other until you understand what your code is doing.
And here’s one way to rotate the matrix 90° clockwise (there are others, of course):
def rotate(matrix):
if not matrix or len(matrix) != len(matrix[0]):
return False
length = len(matrix)
for i in range(length): (1)
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(length): (2)
for j in range(length // 2): (3)
matrix[i][j], matrix[i][length - 1 - j] = \
matrix[i][length - 1 - j], matrix[i][j]
return matrix
print(rotate(make_matrix(4)))
Notes:
- Transpose the matrix.
- Reverse the columns. To rotate the matrix 90° counterclockwise, reverse the rows instead.
- This is reversing the row. The same
forloop be used for reversing a string (see below).
Transposition
Let’s look at the transposition that occurs in the first for loop. Comment out the first second for loop and inspect the results:
def rotate(matrix):
if not matrix or len(matrix) != len(matrix[0]):
return False
length = len(matrix)
for i in range(length):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# for i in range(length):
# for j in range(length // 2):
# matrix[i][j], matrix[i][length - 1 - j] = \
# matrix[i][length - 1 - j], matrix[i][j]
return matrix
for n in range(3, 6):
print(rotate(make_matrix(n)))
+-----------+ +-----------+
| 1 | 2 | 3 | | 1 | 4 | 7 |
|-----------| |-----------|
| 4 | 5 | 6 | =====> | 2 | 5 | 8 |
|-----------| |-----------|
| 7 | 8 | 9 | | 3 | 6 | 9 |
+-----------+ +-----------+
+-------------------+ +-------------------+
| 1 | 2 | 3 | 4 | | 1 | 5 | 9 | 13 |
|-------------------| |-------------------|
| 5 | 6 | 7 | 8 | | 2 | 6 | 10 | 14 |
|-------------------| =====> |-------------------|
| 9 | 10 | 11 | 12 | | 3 | 7 | 11 | 15 |
|-------------------| |-------------------|
| 13 | 14 | 15 | 16 | | 4 | 8 | 12 | 16 |
+-------------------+ +-------------------+
+------------------------+ +------------------------+
| 1 | 2 | 3 | 4 | 5 | | 1 | 6 | 11 | 16 | 21 |
|------------------------| |------------------------|
| 6 | 7 | 8 | 9 | 10 | | 2 | 7 | 12 | 17 | 22 |
|------------------------| |------------------------|
| 11 | 12 | 13 | 14 | 15 | =====> | 3 | 8 | 13 | 18 | 23 |
|------------------------| |------------------------|
| 16 | 17 | 18 | 19 | 20 | | 4 | 9 | 14 | 19 | 24 |
|------------------------| |------------------------|
| 21 | 22 | 23 | 24 | 25 | | 5 | 10 | 15 | 20 | 25 |
+------------------------+ +------------------------+
Ever since I was a little kid, I’ve loved patterns. Little did I know that that would prove to be an invaluable quality later in my second act as a programmer. We can look at the patterns in the data grids above to perhaps glean some insights into what is happening. And these patterns are occurring because the data is sequential.
For instance, note that the transposition for each row increases in direct relation to the N size of the grid. Just for fun, let’s look at how we can use this knowledge to do the transposition in a different way:
def transpose(matrix):
length = len(matrix)
mat = []
for n in range(length): (1)
mat.append([matrix[0][n]])
for row in mat:
i = 0
while i < length - 1: (2)
row.append(row[i] + length) (3)
i += 1
return matrix
Notes:
- Using the
length, create the rows and set the first value of each row (its cell) to the next integer in the sequence. Refer to the matrices art above to help visualize this. - The
lengthis one-based, so we need to subtract one to prevent any out-of-bounds errors! - Simply add the
lengthto each previous value for all the cells in the row. Again, this works because the matrix values are a sequence which we can leverage using thelengthvalue.
We can probably lose the first for loop, though. Since the data is a sequence, we already have the information needed to initiate the first value of each row by looking at the length property.
def transpose(length): (1)
matrix = []
for n in range(length): (2)
row = [n + 1] (3)
i = 0
while i < length - 1: (4)
row.append(row[i] + length)
i += 1
matrix.append(row)
return matrix
Notes:
- We don’t need the
matrixitself, just itslength. - This is now the only
forloop. We’ve essentially collapsed both of the prior two into just this one. - Seed each row with its initial value, which will be the next subsequent value in the sequence. We add one because the
forloop is zero-based (which can be changed obviously and is just an implementation detail). - We re-use the same
whileloop here.
However, the previous implementation is not using the matrix that was created in the make_matrix function but creating its own. This, of course, invalidates our invariant of rotating the matrix in-place, so let’s look at another implementation that does just this:
def transpose(matrix): (1)
length = len(matrix)
for i, row in enumerate(matrix):
row[0] = i + 1 (2)
for j in range(1, length): (3)
row[j] = row[j - 1] + length (4)
return matrix
Notes:
- We’re back to passing in the existing
matrix. - Seed each row with its initial value, which will be the next subsequent value in the sequence. We add one because the
forloop is zero-based (which can be changed obviously and is just an implementation detail). - Since the length of the matrix is the same as that of each of its rows (i.e.,
matrix[0],matrix[1], etc.), we just re-use thelengthvariable here instead of calculating the length of eachrow. - Add the previous value in the row to the
length.
Lastly, if we wanted to be cheeky, we could now rewrite the rotate function to use this new transpose helper function:
def rotate(matrix):
if not matrix or len(matrix) != len(matrix[0]):
return False
matrix = transpose(matrix)
for i in range(length):
for jj in range(length // 2):
matrix[i][jj], matrix[i][length - 1 - jj] = \
matrix[i][length - 1 - jj], matrix[i][jj]
return matrix
In Reverse
Now, let’s take a look at the second for loop that reverses each row. But first, let’s use the same loop to reverse a string:
def reverse_string(string):
arr = list(string)
length = len(arr)
for i in range(length // 2):
arr[i], arr[length - 1 - i] = arr[length - 1 - i], arr[i]
return "".join(arr)
Neat!
We can see this in action by commenting-out the first for loop:
def rotate(matrix):
if not matrix or len(matrix) != len(matrix[0]):
return False
length = len(matrix)
# for i in range(length):
# for j in range(i):
# matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(length):
for j in range(length // 2):
matrix[i][j], matrix[i][length - 1 - j] = \
matrix[i][length - 1 - j], matrix[i][j]
return matrix
for n in range(3, 6):
print(rotate(make_matrix(n)))
+-----------+ +-----------+
| 1 | 2 | 3 | | 3 | 2 | 1 |
|-----------| |-----------|
| 4 | 5 | 6 | =====> | 6 | 5 | 4 |
|-----------| |-----------|
| 7 | 8 | 9 | | 9 | 8 | 7 |
+-----------+ +-----------+
+-------------------+ +-------------------+
| 1 | 2 | 3 | 4 | | 4 | 3 | 2 | 1 |
|-------------------| |-------------------|
| 5 | 6 | 7 | 8 | | 8 | 7 | 6 | 5 |
|-------------------| =====> |-------------------|
| 9 | 10 | 11 | 12 | | 12 | 11 | 10 | 9 |
|-------------------| |-------------------|
| 13 | 14 | 15 | 16 | | 16 | 15 | 14 | 13 |
+-------------------+ +-------------------+
+------------------------+ +------------------------+
| 1 | 2 | 3 | 4 | 5 | | 5 | 4 | 3 | 2 | 1 |
|------------------------| |------------------------|
| 6 | 7 | 8 | 9 | 10 | | 10 | 9 | 8 | 7 | 6 |
|------------------------| |------------------------|
| 11 | 12 | 13 | 14 | 15 | =====> | 15 | 14 | 13 | 12 | 11 |
|------------------------| |------------------------|
| 16 | 17 | 18 | 19 | 20 | | 20 | 19 | 18 | 17 | 16 |
|------------------------| |------------------------|
| 21 | 22 | 23 | 24 | 25 | | 25 | 24 | 23 | 22 | 21 |
+------------------------+ +------------------------+
If we’re so inclined, we can also abstract this into a helper function:
def reverse(matrix):
length = len(matrix)
for i in range(length):
for j in range(length // 2):
matrix[i][j], matrix[i][length - 1 - j] = \
matrix[i][length - 1 - j], matrix[i][j]
return matrix
The rotate function now becomes:
def rotate(matrix):
return reverse(transpose(matrix))
We’re now heading down the path towards functional programming. We’ve separated the helper bits into discrete pieces and named them appropriately, which greatly facilitates understanding and maintenance. Further, rotate and its helpers have an arity of one which improves their use as potential building blocks for other programs.
It’s good to isolate parts of a program to see what each little fella is doing. After all, it’s not pre-ordained that this stuff will be fully understood without first exercising a bit of freewill.
Conclusion
This has now become longer than I originally intended, so I think I’ll put my pencil down and tie a bow on this one. More could be said, and if I’m so inclined I’ll revisit this and update it.