Problem Statement
Given a square matrix of size N x N, the task it to rotate the matrix by 90 degree clockwise. This means that each element of the matrix should be moved in a new position such that the rows become columns, and the order of elements in row is reversed.
LeetCode
Examples
Example 1:
Input: matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
Output: matrix = [
[7, 4, 1],
[8, 5, 2],
[9, 6, 3]
]
Explanation:
1 2 3
4 5 6
7 8 9
is rotated 90 degree to right (clockwise)
will turn it into following:
7 4 1
8 5 2
9 6 3Example 1:
Input: matrix = [
[0, 1, 1, 2],
[2, 0, 3, 1],
[4, 5, 0, 5],
[5, 6, 7, 0]
]
Output: [
[5, 4, 2, 0],
[6, 5, 0, 1],
[7, 0, 3, 1],
[0, 5, 1, 2]
]Different Approaches
1️⃣ Brute Force Approach
Take another matrix of same size and then take the first row of the matrix and put it in the last column of the dummy matrix, take the second row of the matrix, and put it in the second last column of the matrix and so on.
Intuition:
In the brute force approach, we create a new matrix where each element in the original matrix is directly mapped to its new position in the rotated matrix. Specifically:
- The element at position
(i, j)in the original matrix will be moved to position(j, N-1-i)in the new matrix.
Steps:
- Create a new
N x Nmatrix (result matrix) to store the rotated matrix. - For every element at position
(i, j)in the original matrix:- Move it to position
(j, N-1-i)in the result matrix.
- Move it to position
- After constructing the rotated matrix, copy the result matrix back into the original matrix (if required).
Code:
#include<bits/stdc++.h>
using namespace std;
vector < vector < int >> rotate(vector < vector < int >> & matrix) {
int n = matrix.size();
// Create a new matrix to store the rotated version
vector <vector<int>> rotated(n, vector<int>(n, 0));
// Fill the result matrix with rotated values
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
rotated[j][n - i - 1] = matrix[i][j];
}
}
return rotated;
}
int main() {
vector < vector < int >> arr;
arr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
vector < vector < int >> rotated = rotate(arr);
cout << "Rotated Image" << endl;
for (int i = 0; i < rotated.size(); i++) {
for (int j = 0; j < rotated[0].size(); j++) {
cout << rotated[i][j] << " ";
}
cout << "n";
}
}Complexity Analysis:
- Time Complexity:
O(N * N)to linearly iterate and put in dummy matrix. - Space Complexity:
O(N * N)because of dummy matrix.
2️⃣ Optimal Approach
Intuition:
- Step 1: Transposing the Matrix Transposition of a matrix means flipping it over its diagonal. For an
N x Nmatrix, the element at position(i, j)is swapped with the element at position(j, i). - Step 2: Reversing Each Row Once the matrix is transposed, every row is reversed. This reversal effectively rotates the matrix by 90 degrees clockwise.
Algorithm:
- Transpose the matrix (transposing means changing column to rows and rows to columns).
- Reverse each row of the matrix.
Dry Run:
Initialization:
+-----+-----+-----+
matrix = | 1 | 2 | 3 |
+-----+-----+-----+
| 4 | 5 | 6 |
+-----+-----+-----+
| 7 | 8 | 9 |
+-----+-----+-----+Transpose:
+-----+-----+-----+
matrix = | 1 | 4 | 7 |
+-----+-----+-----+
| 2 | 5 | 8 |
+-----+-----+-----+
| 3 | 6 | 9 |
+-----+-----+-----+Reverse Every Row:
+-----+-----+-----+
matrix = | 7 | 4 | 1 |
+-----+-----+-----+
| 8 | 5 | 2 |
+-----+-----+-----+
| 9 | 6 | 3 |
+-----+-----+-----+
Code:
#include<bits/stdc++.h>
using namespace std;
void rotate(vector < vector < int >> & matrix) {
int n = matrix.size();
//transposing the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
//reversing each row of the matrix
for (int i = 0; i < n; i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
}
int main() {
vector < vector < int >> arr;
arr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
rotate(arr);
cout << "Rotated Image" << endl;
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < arr[0].size(); j++) {
cout << arr[i][j] << " ";
}
cout << "n";
}
}
Complexity Analysis:
- Time Complexity:
O(N * N )+O(N * N)- One
O(N * N)is for transposing. - Other for reversing the matrix.
- One
- Space Complexity:
O(1)