Cracking the coding interview 1.7 - Rotate matrix by 90 degrees

Question

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.

Answer 1

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.

Answer 2

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]