Rotate Matrix

Difficulty: Medium

Asked in: Google

Understanding the problem

You are given an N x N 2D matrix representing an image. Write a program to rotate the image by 90 degrees (clockwise).

Problem Note

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly and you can't use extra space.

Example 1

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

Example 2

Input:
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
]
Output: 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]
]

You may try to solve the problem here .

Solutions

We will be discussing two approaches for the problem

Transpose Matrix and Reverse Rows
In-place Rotate

Transpose and Rotate

The idea is to first, transpose the matrix and then flip it symmetrically. For instance,

1  2  3             
4  5  6
7  8  9

after transpose, it will be swap(matrix[i][j], matrix[j][i]) i.e. make the rows as columns and columns as rows.

1  4  7
2  5  8
3  6  9

Then flip the matrix along the vertical axis. swap(matrix[i][j], matrix[i][N-1-j]

7  4  1
8  5  2
9  6  3

Visualization

Solution steps

Take the transpose of the matrix with m rows and n columns.

Go to every pair of i and j indices within the range of its length.
swap matrix[i][j] with matrix[j][i] .

2. Reverse each row of the matrix

Inplace rotate each row by swapping matrix[i][j] with matrix[i][N-1-j]

Pseudo Code

// Driver function, N represent the dimensions of matrix
void rotateMatrix(int[][] matrix, int N) {
    // take transpose of matrix
    for(int i = 0 to N){
        for(int j = i to N){
            int temp = matrix[i][j]
            matrix[i][j] = matrix[j][i]
            matrix[j][i] = temp
        }
    }
    // perform rotation of each row
    for(int i = 0 to N){
        for(int j = 0 to N/2){
            int temp = matrix[i][j]
            matrix[i][j] = matrix[i][N-1-j]
            matrix[i][N-1-j] = temp
        }
    }
}

Critical Ideas to Think

How did we find the transpose of the matrix?
Why are we performing swapping till N/2 while rotating each row?
Will this algorithm work if the matrix dimension is not N x N ?
If we first perform the rotation of rows and then perform its transpose, then will the algorithm work? If yes, Why?
What changes will we make to perform the rotation in the anticlockwise direction?

Complexity Analysis

Time Complexity — O(N²) (Why?)

Space Complexity — O(1) Due to in-place rotation of matrix.

In-place Rotate

If you will notice the input and resultant matrices, you will find that,

The first row of the source matrix is the last column of the destination matrix. Similarly, the second row of the source matrix is the second last column of destination and so … on the last row of the source is the last column of the destination matrix.

So, if we consider the outer most elements of the matrix as a layer then a N x N matrix will have ceil(N/2) square cycles. For example, a 6 x 6 matrix will have 3 cycles. The first cycle is formed by its 1st row, last column, last row and 1st column. The second cycle is formed by 2nd row, second-last column, second-last row and 2nd column and so on. (You can take help from the above figure where N = 5)

The idea is for each square cycle, we swap the elements involved with the corresponding cell in the matrix in clockwise direction i.e. from top to right, left to top, bottom to the left and from right to the bottom, one at a time.

Visualization

Solution Steps

Consider all squares/cycles one by one, there will be maximum Ceil( N/2) cycles for any N .
For each cycle, store the first element of the top row in a temp variable, then perform

matrix[low][i] = matrix[i][high]
matrix[i][high] = matrix[high][N-i-1]
matrix[high][N-i-1] = matrix[N-i-1][low]
matrix[N-i-1][low] = temp

Pseudo Code

void rotateMatrix(int[][] matrix, int N) {
    int layer  = 0
    while(layer < N/2){ 
        int low = layer
        int high = N - 1 - layer
        for (int i = low to high){
        // Swapping elements after each iteration in clockwise
            int temp = matrix[low][i]
            matrix[low][i] = matrix[N-1-i][low]
            matrix[N-1-i][low] = matrix[N-1-low][N-1-i] 
            matrix[N-1-low][N-1-i] = matrix[i][N-1-low]
            matrix[i][N-1-low] = temp
        }
        layer = layer + 1
    }
}