# Cracking the coding interview 1.7 - Rotate matrix by 90 degrees

The question asks to rotate an image/matrix by 90 degrees. Ideally it asks to do it in place but before that I decided to do it using extra space because this is my first time working with matrices.

question: while using extra space, could this have been any better?

def rotate_m1(matrix, d):
"""
with extra space
for each row in the orginal matrix, the items position in that row
will be its row in the new matrix. Its position in the new row will be determined
by 'l' (matrix row length), which decrements after each loop.

e.g.
1,2
3,4

the loop goes through and maps the top row to the outside of a new matrix. i.e.

i = 0 # row
j = 0 # col // its postion in the row
l = d-1 # d = the dimensions of the matrix
matrix[i][j] = 1

in the new matrix the postion of matrix[i][j] (1) will be:

new_matrix[j][l]; j being its postion in its original row, so in this case 1 was in postion 0 in
the original matrix, and l is the outermost row of the new matrix becuse (in this example) during
the first loop l = 2-1.

after the first row is mapped, we take one away from l to map the next row to the row before
the outer most row in the new matrix (d-2)
"""

m2 = [[0 for x in range(d)] for y in range(d)] # construct new matrix
l = d-1

for i in range(len(matrix)):
for j in range(len(matrix[i])):
m2[j][l] = matrix[i][j]

l -= 1
print m2


input/ouptut:

input:
[[1,2,3],
[4,5,6],
[7,8,9]]

output:
[[7, 4, 1],
[8, 5, 2],
[9, 6, 3]]


I've added some extra info about how I came to the solution in the code comment.

Most of your code looks good. I have a few remarks, though.

The name of your function rotate_m1 is misleading. What does the m1 mean at all? Additionally, your function prints the result. It should not do that. Instead, it should either rotate the matrix in-place, or alternatively return the rotated matrix. That way, you can use the result further:

print(rotate(rotate(matrix)))


With your current code, thisis not possible.

The docstring of your function is very long. This docstring should be written for a specific target audience, which is the users of the function. The users only need to know:

"""Returns a copy of the given matrix, rotated clockwise by 90 degrees.

Example: [[1, 2, 3], [4, 5, 6]] is rotated to [[4, 1], [5, 2], [6, 3]]
"""


The implementation details do not belong in the behavioral description of the function.

Note that I chose a non-square example on purpose. If you rotate the matrix in-place, the matrix has to be square, but when you create a copy, you can also handle arbitrary rectangular matrices. Your code currently doesn't do this, but it should.

My standard disclaimer about CtCI: Don't trust that book. It contains many typos and inefficient, English-America-centric code. The "solution" code is often not indented properly, variables are not named carefully, edge cases are forgotten, and so on. I would not hire someone who learned from that book alone.

• Wouldn't you agree that adding a parameter comment on 'matrix' in the docstring would be helpful as well? i.e. square matrix, or (n x m) matrix, perhaps max practical size. – SteveJ May 9 '18 at 5:18
• No, I would not add that information. I would expect that the code can handle arbitrary matrices (which by the Wikipedia definition have to be rectangular). Mentioning the dimension n x m is as pointless as declaring a variable and then not using it. The maximum practical size is obvious: if the input matrix fits into memory, the output matrix takes about the same space. The space requirements of a matrix are not peculiar to rotation, therefore they need to be documented somewhere else. – Roland Illig May 9 '18 at 5:32

You can do the rotate in one line.

d = 3
m1 = [[y*d+x+1 for x in range(d)] for y in range(d)]
m2 = [list(r) for r in zip(*m1[::-1])]

[print(r) for r in m1]
[print(r) for r in m2]


and...I don't think you want to pass the matrix, and d. You can get d from the matrix - passing in both you run the risk of a mismatch.

[Edit: Since pasting into the interpreter is not as assumed as I thought]

m1 =
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

m2 =
[7, 4, 1]
[8, 5, 2]
[9, 6, 3]


[Edit: ...for completeness]

def rotate_matrix(matrix):
return [list(r) for r in zip(*matrix[::-1])]

def print_matrix(matrix, name):
print(f"{name} = ")
[print(r) for r in matrix]

if __name__ == "__main__":
h, w = 3, 4
m1 = [[y * w + x + 1 for x in range(w)] for y in range(h)]
print_matrix(m1, "original")
print_matrix(rotate_matrix(m1), "rotated once")
print_matrix(rotate_matrix(rotate_matrix(m1)), "rotated twice")
print_matrix(rotate_matrix(rotate_matrix(rotate_matrix(rotate_matrix(m1)))), "back to the beginning")


Yields:

original =
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]

rotated once =
[9, 5, 1]
[10, 6, 2]
[11, 7, 3]
[12, 8, 4]

rotated twice =
[12, 11, 10, 9]
[8, 7, 6, 5]
[4, 3, 2, 1]

back to the beginning =
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]

• I don't see any input matrix in your code. – Roland Illig May 9 '18 at 4:37
• @RolandIllig; I wrote it so it could be pasted into an interpreter, but I added the results for clarity. – SteveJ May 9 '18 at 4:55
• Ah, now I understand. If you had named your variables properly, e.g. input androtated, it would have been much clearer. And an empty line between the setup and the rotation would have helped also. – Roland Illig May 9 '18 at 5:00