You are given an \(n \times n\) 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = 
[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
],

rotate the input matrix in-place such that it becomes:
[
  [7, 4, 1],
  [8, 5, 2],
  [9, 6, 3]
]

Example 2:

Given input matrix = 
[
  [ 5,  1,  9, 11],
  [ 2,  4,  8, 10],
  [13,  3,  6,  7],
  [15, 14, 12, 16]
],

rotate the input matrix in-place such that it becomes:
[
  [15, 13,  2,  5],
  [14,  3,  4,  1],
  [12,  6,  8,  9],
  [16,  7, 10, 11]
]

Solution:

The traditional approach to this problem is to transpose the array, and then reflect the matrix across the vertical axis of symmetry. While this may be the most intuitive way to approach the problem, it requires us to iterate through the matrix twice. Sure, in terms of asymptotic complexity this is an irrelevant factor of 2; however, for large enough n, this might add a few milliseconds.

We can actually solve this with a single pass through the array. First, from the intuition that we can transpose and then reflect the matrix, we can see that

# Rotate [i][j] by 90 degrees
matrix[i][j] == rotate(matrix)[j][n-1-i]

# Rotate [j][n-1-i] by 90 degrees
matrix[j][n-1-i] == rotate(matrix)[n-1-i][n-1-j]

# Rotate [n-1-i][n-1-j] by 90 degrees
matrix[n-1-i][n-1-j] == rotate(matrix)[n-1-j][i]

# Rotate [n-1-j][i] by 90 degrees
matrix[n-1-j][i] == rotate(matrix)[i][j]

This should make sense, since once we rotate four times we’re back to the pair of indexes that we started with. Then, for a given pair of indexes, (i, j), we can determine four of the values in the resulting rotated matrix. The trick is to figure out how to iterate over the values of i and j such that we hit the entire matrix.

Well, let’s say we go over each of the elements in row i of the matrix. In this case,

  • we rotate the i-th row to get the (n-1-i)-th column of the rotated matrix,
  • we rotate the (n-1-i)-th column to get the (n-1-i)-th row of the rotated matrix,
  • we rotate the (n-1-i)-th row to get the i-th column of the rotated matrix,
  • and we rotate the i-th column to get the i-th row of the rotated matrix

Effectively, we’ve rotated the i-th layer of the matrix. Once we do this, the problem is reduced to the (n-2i) case. In the case where n is odd,there will be a single element in the center of the matrix that is left untouched by the rotation; however, in the case where n is even, every element of the matrix will be rotated.

def rotate(matrix):
    """
    :type matrix: List[List[int]]
    :rtype: void Do not return anything, modify matrix in-place instead.
    """
    n = len(matrix)
    for i in xrange(n/2):
        for j in xrange(i, n - 1 - i):
            # Rotate (i,j) to (j, n-1-i)
            temp = matrix[j][n-1-i]
            matrix[j][n-1-i] = matrix[i][j]

            # Rotate (j, n-1-i) to (n-1-i, n-1-j)
            temp_ = matrix[n-1-i][n-1-j]
            matrix[n-1-i][n-1-j] = temp
            
            # Rotate (n-1-i, n-1-j) to (n-1-j, i)
            temp = matrix[n-1-j][i]
            matrix[n-1-j][i] = temp_

            # Rotate (n-1-j, i) to (i, j)
            matrix[i][j] = temp

From here, it’s rather easy to see that we only ever read from matrix[i][j] exactly once and write to matrix[i][j] exactly once for a given pair of indexes (i, j).

Complexity Analysis

  • Time: \(O(n^2)\)
  • Space: \(O(1)\)