Cracking the Coding Interview - Rotate Image 90 Degrees

1.6 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rtate the image by 90 degrees. Can you do this in place?

In place 90 degree rotation

def one_dot_six_1(matrix):
    n = len(matrix)
    rows, cols = n, n
    mid = n // 2
    for row in range(mid): 
        for col in range(row, cols - row - 1):
            # 3 x 3 example
            ax, ay = row, col # 0 0
            bx, by = ay, cols - ax - 1 # 0 2
            cx, cy = by, cols - bx - 1 # 2 2
            dx, dy = cy, cols - cx - 1 # 2 0
    
            # save values
            a = matrix[ax][ay]
            b = matrix[bx][by]
            c = matrix[cx][cy]
            d = matrix[dx][dy]
            
            # rotate them
            matrix[bx][by] = a
            matrix[cx][cy] = b
            matrix[dx][dy] = c
            matrix[ax][ay] = d
    return matrix

Here’s a few insights and gotchas I ran into writing this solution:

  • Don’t rotate the last column when you’re running through the first row because it’s already been updated
  • Think about the destintination coordinates in respect to the source coordinates. You can apply this relationship to every “face” of the matrix
  • Start small. Test with a 3 x 3 matrix. Start by moving a single element without loops. Then try moving an entire row.