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

Key takeaway: A famous matrix-based problem that can be solved in place using loop and properties of matrix.

Let’s understand the problem

Given an n x n square matrix, write a program to rotate matrix by 90 degrees in the anticlockwise direction. It is expected to rotate matrix in place. In other words, we have to perform rotation by modify the 2D matrix directly.

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 the transpose of the matrix
• Efficient in-place approach using nested loops

A brute force approach using extra space

Solution idea and steps

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

• The first row in input matrix: 1, 2, 3, 4,
• The first column in 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 above observation.

• The first row of input matrix = The first column of output matrix in reverse order
• The second row of input matrix = The second column of output matrix in reverse order and so on.
• The last row of input matrix = The last column of 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 input matrix using two nested loops which takes O(n²) time. So time complexity = O(n²). We are using an extra matrix takes of size n x n, so space complexity = O(n²).

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

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

Solution idea

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

After the rotation of a matrix by 90 degrees anticlockwise:

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

So if we take the transpose of input matrix:

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

So one solution idea would be: If we take the transpose of 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 :  A transpose of a matrix is a matrix flipped over its diagonal, i.e., the row index of an element becomes the column index and vice versa. So, we need to swap 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 the transposed matrix column-wise: We run two nested loops where outer loop scans each column from 0 to n - 1 and 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
    }
}

Time and space complexity analysis

We are traversing input matrix twice using nested loops. Time complexity = Time complexity of converting input matrix into a transpose + Time complexity of reversing transposed matrix column-wise = O(n²) + O(n²) = O(n²). Space Complexity = O(1), as no extra memory is needed.

An efficient approach using nested loops (In-place)

Solution idea and steps

There is another idea that can solve this problem in place. If we track initial and final position of each element after the rotation, we can get a solution pattern.

So here are critical conservations for the solution:

1. There is total n/2 squares in a 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 first row, last column, last row, and first column. Then we process the second square formed by second row, second-last column, second-last row, and second column. And so on, we move from the outer square to innermost square.
2. In each square, elements are moved in a cycle of 4 elements. We swap elements involved in each cycle in the anticlockwise direction, i.e., from right to the top, top to left, left to bottom, and bottom to 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 positions of all such pairs of four elements to rotate the matrix by 90 degrees in anticlockwise order.
3. Element at position (i, j) will go to position (n - 1 - j, i).
4. Element at position (n - 1 - j, i) will go to position (n - 1 - i, n - 1 - j).
5. Element at position (n - 1 - i, n - 1 - j) will go to position (j, n - 1 - i).
6. 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
        }
    }
}

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. Time complexity = O(n²). Space complexity = O(1), as no extra memory is needed.

Here is a precise mathematical analysis of the above code. For i = 0, inner loop is running n times, for i = 1, inner loop is running n - 2 times, for i = 2, inner loop is running n - 4 times, and so on! So total number of loop iterations = n + (n - 2) + (n - 4) + .... + 1 = 1 + 3 + 5 + .... + n - 4 + n - 2 + n (Note: This sequence is an arithmetic series, where last term will be 2 or 1 depending on whether n is even or odd. Suppose n is odd and the last term is 1)

The general formula of the sum of arithmetic series = 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, first term. = 1, total number of terms = n/2, common difference = 2.

If we put these values in the above formula of sum, total number of loop iterations = 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)^2. At each iteration, we are doing O(1) operations. So time complexity = Total number of loop iterations x O(1) = (n/2)^2 * O(1) = O(n^2)

Critical ideas to think about!

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

Comparisons of time and space complexities

• Using extra space: Time = O(n^2), Space = O(n^2)
• Using matrix transpose: Time = O(n^2), Space = O(1)
• Using nested loops (In-place): Time = O(n^2), 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

Please write in the message below, if you find an error or you want to share more insights. Enjoy learning, Enjoy coding, Enjoy algorithms.