Rotate Matrix by 90 Degrees

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

Key takeaway: A well known problem to learn in-place problem solving using 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 i.e. 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
• In-place approach using matrix transpose
• In-place approach  using square wise traversal

Brute force approach  using extra space

Solution idea and steps

If we observe the input and output matrices, we can find this insight: 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 traverse the input matrix to copy elements based on the above observation. Here any element entry (i, j) of the input matrix will go to (n - j - 1, i) entry in the output matrix. Explore and think!

• 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

rotateMatrix(X, n)
    output = n × n matrix

    // Place each element in its position 
    // after a 90° clockwise rotation
    for i from 0 to n - 1
        for j from 0 to n - 1
            output[n - j - 1][i] = X[i][j]

    return output

Time and space complexity analysis

We are traversing the input matrix using two nested loops. So the time complexity = O(n^2). We are using an extra matrix of size n x n, so the space complexity = O(n^2).

In-place approach using matrix transpose

Now the critical questions are: Can we solve the problem without using extra space? Can we observe some pattern in the anticlockwise rotation of the matrix? Let's think!

Solution idea

Let’s go through the same observation from the above approach. After rotating a matrix by 90 degrees anticlockwise, the ith row of the input matrix becomes the ith column in reverse order. This is similar to the idea of exchanging rows and columns (transpose of the matrix) with one difference: We need to just reverse every column after taking the transpose of the input matrix. In other words, if we take the transpose of the input matrix and then 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 given matrix is a square matrix. So we can easily get the transpose 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 (i, j) with the element at (j, i).

for i from 0 to n - 1
    for j from i to n - 1
        swap X[j][i] and X[i][j]

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.

column = 0
while column < n
    i = 0
    j = n - 1

    while i < j
        swap X[i][column] and X[j][column]
        i = i + 1
        j = j - 1

    column = column + 1

Solution pseudocode

rotateMatrix(X, n)
    if n == 0 or n == 1
        return
    // Transpose the matrix across its main diagonal
    for i from 0 to n - 1
        for j from i to n - 1
            swap X[j][i] and X[i][j]
    // Reverse each column to complete the counterclockwise rotation
    column = 0
    while column < n
        i = 0
        j = n - 1

        while i < j
            swap X[i][column] and X[j][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.

In-place approach  using square wise traversal

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

rotateMatrix(X, n)
    // Process the matrix one layer at a time, moving inward
    for i from 0 to (n / 2) - 1
        // Visit each group of four corresponding elements in this layer
        for j from i to n - i - 2
            temp = X[i][j]

            // Move the left element to the top
            X[i][j] = X[n - 1 - j][i]

            // Move the bottom element to the left
            X[n - 1 - j][i] = X[n - 1 - i][n - 1 - j]

            // Move the right element to the bottom
            X[n - 1 - i][n - 1 - j] = X[j][n - 1 - i]

            // Move the saved top element to the right
            X[j][n - 1 - 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!