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 inplace, 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 inplace 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 inplace 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
 Inplace 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][N1j]
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
andj
indices within the range of its length. 
swap
matrix[i][j]
withmatrix[j][i]
.
2. Reverse each row of the matrix

Inplace rotate each row by swapping
matrix[i][j]
withmatrix[i][N1j]
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][N1j]
matrix[i][N1j] = 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 inplace rotation of matrix.
Inplace 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, secondlast column, secondlast 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 anyN
.  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][Ni1]
 matrix[high][Ni1] = matrix[Ni1][low]
 matrix[Ni1][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[N1i][low]
matrix[N1i][low] = matrix[N1low][N1i]
matrix[N1low][N1i] = matrix[i][N1low]
matrix[i][N1low] = temp
}
layer = layer + 1
}
}
Critical Ideas to Think

Why there could be maximum of
N/2
cycles for a particularN
?  How are we performing rotation for each cycle?
 What changes will you make to make the rotation anticlockwise?
Complexity Analysis
Time Complexity — O(N²)
Space Complexity — O(1), Rotation is performed inplace.
Comparison of different solutions
Suggested problems to solve
 Take transpose of M x N size matrix inplace
 Rotate a Matrix by 180 degree
 Rotate the matrix clockwise by K times
 Rotate each ring of matrix anticlockwise by K elements
Please comment down below if you find an improvement in the above explanation.
Happy Coding!