Rotate Matrix by 90 Degrees

Difficulty: Medium, Asked-in: Google, Facebook, Microsoft, Amazon, Morgan Stanley

Key takeaway: This is a well-known matrix problem that can be solved in-place using loops and matrix properties.

Let’s understand the problem

Given an n x n square matrix, write a program to rotate the matrix by 90 degrees in the anti-clockwise direction. The goal is to perform the matrix rotation in place, meaning we need to rotate the matrix without using extra space.

Examples

Important note: Before moving on to solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!

Discussed solution approaches

• Brute force approach using extra space
• Efficient in-place approach using transpose of the matrix
• Efficient in-place approach using nested loops

Brute force approach using extra space

Solution idea and steps

If we observe the input and output matrices, the following pattern would be visible: The first row has turned into the first column in reverse order. Similarly, the second, third, … and last rows have turned into their respective columns in reverse order. For example:

• The first row in the input matrix: 1, 2, 3, 4
• The first column in the output matrix: 4, 3, 2, 1

So one basic idea would be to use an extra matrix of the same size and directly copy elements from the original matrix based on the above observation.

• The first row of the input matrix = The first column of the output matrix in reverse order
• The second row of the input matrix = The second column of the output matrix in reverse order and so on.
• The last row of the input matrix = The last column of the output matrix in reverse order.

Solution pseudocode

int[][] rotateMatrix(int X[][], int n)
{
    int temp[n][n]
    for (int i = 0; i < n; i = i + 1)
    {
        for (int j = 0; j < n; j = j + 1)
        {
            temp[n - j - 1][i] = X[i][j]
        }
   }
   return temp
}

Time and space complexity analysis

In the above approach, we are traversing the input matrix using two nested loops, which take O(n²) time. So the time complexity is O(n²). We are using an extra matrix of size n x n, so the space complexity is O(n²).

As given in the problem description, can we solve the problem without using extra space or in-place? Can we observe some pattern in the anticlockwise rotation of the matrix? Let's think!

An efficient approach using the transpose of the matrix (In-place)

Solution idea

If we deep dive into the input and output, we can find patterns to rotate the matrix by swapping values. Let’s go through the same observation from the above approach.

After the rotation of a matrix by 90 degrees anticlockwise:

• The first row of the input matrix = The first column of the output matrix in reverse order
• The last row of the input matrix = The last column of the output matrix in reverse order

So if we take the transpose of the input matrix:

• The first row of the input matrix = The first column of the output matrix.
• The last row of the input matrix = The last column of the output matrix.

So one solution idea would be: If we take the transpose of the input matrix and reverse each column, we will get the desired matrix rotated by 90 degrees in an anticlockwise direction (Think!).

Solution steps

Convert given matrix into its transpose: The transpose of a matrix is obtained by flipping the matrix over its diagonal, i.e., the row index of an element becomes the column index and vice versa. So we need to swap the elements at position X[i][j] with the element at X[j][i].

for (int i = 0; i < n; i = i + 1) 
{
    for (int j = i; j < n; j = j + 1) 
    {
        swap(X[i][j], X[j][i])
    }
}  

Reverse transposed matrix column-wise: We run two nested loops where the outer loop iterates over each column from 0 to n - 1, and the inner loop reverses each column by swapping values.

int i = 0, j = 0, column = 0
while (column < n)
{
    i = 0, j = n - 1
    while (i < j)
    {
        swap(X[i][column], X[j][column])
        i = i + 1
        j = j - 1
    } 
    column = column + 1
}

Solution pseudocode

void rotateMatrix(int X[][], int n)
{
    if(n == 0 || n == 1)
        return
    
    for (int i = 0; i < n; i = i + 1) 
    {
        for (int j = i; j < n; j = j + 1) 
        {
            swap(X[j][i], X[i][j])
        }
    }    
   
    int i = 0, j = 0, column = 0
    while (column < n)
    {
        i = 0, j = n - 1
        while (i < j)
        {
            swap(X[i][column], X[j][column])
            i = i + 1
            j = j - 1
        } 
        column = column + 1
    }
}

Python implementation

def rotateMatrix(X, n):
    if n == 0 or n == 1:
        return

    for i in range(n):
        for j in range(i, n):
            X[j][i], X[i][j] = X[i][j], X[j][i]

    column = 0
    while column < n:
        i, j = 0, n - 1
        while i < j:
            X[i][column], X[j][column] = X[j][column], X[i][column]
            i = i + 1
            j = j - 1
        column = column + 1

Time and space complexity analysis

We traverse the input matrix twice using nested loops. The time complexity is the sum of the time complexity of converting the input matrix into a transpose and reversing the transposed matrix column-wise, which is O(n²) + O(n²) = O(n²). The space complexity is O(1) since no extra memory is required.

An Efficient Approach Using Nested Loops (In-Place)

Solution Idea and Steps

There is another approach that can solve this problem in place. By tracking the initial and final positions of each element after rotation, we can derive a solution pattern.

So here are critical observations from the above image:

Observation 1: There are a total of n/2 squares in an n x n matrix. So, we can process each square one at a time using a nested loop. We first process the first square formed by the first row, last column, last row, and first column. Then we process the second square formed by the second row, second-last column, second-last row, and second column. And so on, moving from the outer square to the innermost square.

Observation 2: In each square, elements are moved in a cycle of 4 elements. So we need to swap elements involved in each cycle in the anticlockwise direction, i.e., from right to top, top to left, left to bottom, and bottom to the right. In general, the position of elements in any cycle is: (i, j), (n - 1 - j, i), (n - 1 - i, n - 1 - j), and (j, n - 1 - i). So we exchange the positions of all such pairs of four elements to rotate the matrix by 90 degrees in the anticlockwise order.

• The element at position (i, j) will go to position (n - 1 - j, i).
• The element at position (n - 1 - j, i) will go to position (n - 1 - i, n - 1 - j).
• The element at position (n - 1 - i, n - 1 - j) will go to position (j, n - 1 - i).
• The element at position (j, n - 1 - i) will go to position (i, j).

Solution pseudocode

void rotateMatrix(int X[][], int n)
{
    for (int i = 0; i < n / 2; i = i + 1)
    {
        for (int j = i; j < n - i - 1; j = j + 1)
        {
            int temp = X[i][j]
            X[i][j] = X[j][n - 1 - i]
            X[j][n - 1 - i] = X[n - 1 - i][n - 1 - j]
            X[n - 1 - i][n - 1 - j] = X[n - 1 - j][i]
            X[n - 1 - j][i] = temp
        }
    }
}

Python implementation

def rotateMatrix(X, n):
    for i in range(n // 2):
        for j in range(i, n - i - 1):
            temp = X[i][j]
            X[i][j] = X[j][n - 1 - i]
            X[j][n - 1 - i] = X[n - 1 - i][n - 1 - j]
            X[n - 1 - i][n - 1 - j] = X[n - 1 - j][i]
            X[n - 1 - j][i] = temp

Time and space complexity analysis

We are traversing each element of the input matrix only once using a nested loop and fixing its correct position. The time complexity is O(n²), and the space complexity is O(1) since no extra memory is needed.

Here is a precise mathematical analysis of the above code. For i = 0, the inner loop runs n times; for i = 1, the inner loop runs n - 2 times; for i = 2, the inner loop runs n - 4 times, and so on! So the total number of loop iterations is n + (n - 2) + (n - 4) + .... + 1 = 1 + 3 + 5 + .... + n - 4 + n - 2 + n.

The general formula for the sum of an arithmetic series is n/2[2a + (n − 1) × d], where n is the total number of terms, a is the first term, and d is a common difference. So in the sequence 1, 3, 5, ... n - 2, n, the first term is 1, the total number of terms is n/2, and the common difference is 2.

If we put these values in the formula for the sum, the total number of loop iterations is 1 + 3 + 5 + .... + n - 4 + n - 2 + n = n/4 [2 + (n/2 − 1) × 2] = n/4 [2 + (n/2 − 1) × 2] = n/4 * n = (n/2)². At each iteration, we are doing O(1) operations. So the time complexity is Total number of loop iterations * O(1) = (n/2)² * O(1) = O(n²)

Critical ideas to think about!

• Can we solve this problem by first reversing each row and then taking the transpose? If so, please write code for it.
• How can we rotate a matrix in a clockwise direction?
• Is it possible to find the transpose in place using a different approach?
• Can a rectangular matrix of size m x n be rotated by 90 degrees?
• Can we design a general algorithm for rotating a matrix by a multiple of 90 degrees?

Comparisons of time and space complexities

• Using extra space: Time = O(n²), Space = O(n²)
• Using matrix transpose: Time = O(n²), Space = O(1)
• Using nested loops (In-place): Time = O(n²), Space = O(1)

Matrix-based problems for practice

• Print a matrix in a spiral form
• Search in a row-wise sorted 2D matrix
• Find the row with the maximum number of 1s
• Set matrix zeroes
• Conway’s game of life problem

If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!