In-place rotate matrix by 90 degrees in a clockwise direction
Given a square matrix, rotate the matrix by 90 degrees in a clockwise direction. The transformation should be done in-place and in quadratic time.
For example,
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Output:
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
The idea is to in-place convert the matrix into its transpose first. If we swap the first column with the last column, the second column with the second last column, and so on… we will get our desired matrix.
Following is the implementation in C++, Java, and Python based on the above idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <iostream> #include <algorithm> #include <vector> #include <iomanip> using namespace std; // In-place rotate it by 90 degrees in a clockwise direction void rotate(vector<vector<int>> &mat) { // `N × N` matrix int N = mat.size(); // base case if (N == 0) { return; } // Transpose the matrix for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { swap(mat[i][j], mat[j][i]); } } // swap columns for (int i = 0; i < N; i++) { for (int j = 0; j < N/2; j++) { swap(mat[i][j], mat[i][N - j - 1]); } } } // Function to print the matrix void printMatrix(vector<vector<int>> const &mat) { for (auto &row: mat) { for (auto &i: row) { cout << setw(3) << i; } cout << endl; } cout << endl; } int main() { vector<vector<int>> mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; rotate(mat); printMatrix(mat); return 0; } |
Output:
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
import java.util.Arrays; class Main { // In-place rotate it by 90 degrees in a clockwise direction public static void rotate(int[][] mat) { // base case if (mat == null || mat.length == 0) { return; } // `N × N` matrix int N = mat.length; // Transpose the matrix for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { int temp = mat[i][j]; mat[i][j] = mat[j][i]; mat[j][i] = temp; } } // swap columns for (int i = 0; i < N; i++) { for (int j = 0; j < N / 2; j++) { int temp = mat[i][j]; mat[i][j] = mat[i][N - j - 1]; mat[i][N - j - 1] = temp; } } } public static void main(String[] args) { int[][] mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; rotate(mat); for (var r: mat) { System.out.println(Arrays.toString(r)); } } } |
Output:
[13, 9, 5, 1]
[14, 10, 6, 2]
[15, 11, 7, 3]
[16, 12, 8, 4]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
# In-place rotate it by 90 degrees in a clockwise direction def rotate(mat): # base case if not mat or not len(mat): return # `N × N` matrix N = len(mat) # Transpose the matrix for i in range(N): for j in range(i): temp = mat[i][j] mat[i][j] = mat[j][i] mat[j][i] = temp # swap columns for i in range(N): for j in range(N // 2): temp = mat[i][j] mat[i][j] = mat[i][N - j - 1] mat[i][N - j - 1] = temp if __name__ == '__main__': mat = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16] ] rotate(mat) for r in mat: print(r) |
Output:
[13, 9, 5, 1]
[14, 10, 6, 2]
[15, 11, 7, 3]
[16, 12, 8, 4]
If we were asked to rotate the matrix in an anti-clockwise manner, we could easily do that, too, using the same logic. The only difference is that instead of swapping columns, we swap rows.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <iostream> #include <algorithm> #include <vector> #include <iomanip> using namespace std; // In-place rotate it by 90 degrees in an anti-clockwise direction void rotate(vector<vector<int>> &mat) { // `N × N` matrix int N = mat.size(); // base case if (N == 0) { return; } // Transpose the matrix for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { swap(mat[i][j], mat[j][i]); } } // swap rows for (int i = 0; i < N/2; i++) { for (int j = 0; j < N; j++) { swap(mat[i][j], mat[N - i - 1][j]); } } } // Function to print the matrix void printMatrix(vector<vector<int>> const &mat) { for (auto &row: mat) { for (auto &i: row) { cout << setw(3) << i; } cout << endl; } cout << endl; } int main() { vector<vector<int>> mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; rotate(mat); printMatrix(mat); return 0; } |
Output:
4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
import java.util.Arrays; class Main { // In-place rotate it by 90 degrees in an anti-clockwise direction public static void rotate(int[][] mat) { // base case if (mat == null || mat.length == 0) { return; } // `N × N` matrix int N = mat.length; // Transpose the matrix for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { // swap `mat[i][j]` with `mat[j][i]` int temp = mat[i][j]; mat[i][j] = mat[j][i]; mat[j][i] = temp; } } // swap rows for (int i = 0; i < N/2; i++) { for (int j = 0; j < N; j++) { // swap `mat[i][j]` with `mat[N-i-1][j]` int temp = mat[i][j]; mat[i][j] = mat[N-i-1][j]; mat[N-i-1][j] = temp; } } } public static void main(String[] args) { // `N × N` matrix int[][] mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; rotate(mat); for (var r: mat) { System.out.println(Arrays.toString(r)); } } } |
Output:
[4, 8, 12, 16]
[3, 7, 11, 15]
[2, 6, 10, 14]
[1, 5, 9, 13]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
# In-place rotate it by 90 degrees in an anti-clockwise direction def rotate(mat): # base case if not mat or not len(mat): return # `N × N` matrix N = len(mat) # Transpose the matrix for i in range(N): for j in range(i): # swap `mat[i][j]` with `mat[j][i]` temp = mat[i][j] mat[i][j] = mat[j][i] mat[j][i] = temp # swap rows for i in range(N // 2): for j in range(N): # swap `mat[i][j]` with `mat[N-i-1][j]` temp = mat[i][j] mat[i][j] = mat[N - i - 1][j] mat[N - i - 1][j] = temp if __name__ == '__main__': # `N × N` matrix mat = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16] ] rotate(mat) for r in mat: print(r) |
Output:
[4, 8, 12, 16]
[3, 7, 11, 15]
[2, 6, 10, 14]
[1, 5, 9, 13]
The time complexity of the proposed solution is O(N2) for an N × N matrix and doesn’t require any extra space.
Exercise: In-place rotate the matrix by 180 degrees
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)