Problem Statement: Given a matrix, your task is to rotate the matrix 90 degrees clockwise.
Note: Rotate matrix 90 degrees anticlockwise
Examples:
Example 1: Input: [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Explanation: Rotate the matrix simply by 90 degree clockwise and return the matrix. Example 2: Input: [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output:[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] Explanation: Rotate the matrix simply by 90 degree clockwise and return the matrix
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1:Brute force
Approach: Take another dummy matrix of n*n, 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.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
vector < vector < int >> rotate(vector < vector < int >> & matrix) {
int n = matrix.size();
vector < vector < int >> rotated(n, vector < int > (n, 0));
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";
}
}Output:
Rotated Image
7 4 1
8 5 2
9 6 3
Time Complexity: O(N*N) to linearly iterate and put it into some other matrix.
Space Complexity: O(N*N) to copy it into some other matrix.
Java Code
import java.util.*;
class TUF {
static int[][] rotate(int[][] matrix) {
int n = matrix.length;
int rotated[][] = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
rotated[j][n - i - 1] = matrix[i][j];
}
}
return rotated;
}
public static void main(String args[]) {
int arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int rotated[][] = rotate(arr);
System.out.println("Rotated Image");
for (int i = 0; i < rotated.length; i++) {
for (int j = 0; j < rotated.length; j++) {
System.out.print(rotated[i][j] + " ");
}
System.out.println();
}
}
}Output:
Rotated Image
7 4 1
8 5 2
9 6 3
Time Complexity: O(N*N) to linearly iterate and put it into some other matrix.
Space Complexity: O(N*N) to copy it into some other matrix.
Python Code
from typing import List
def rotate(matrix: List[List[int]]) -> List[List[int]]:
n = len(matrix)
rotated = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
rotated[j][n - i - 1] = matrix[i][j]
return rotated
if __name__ == "__main__":
arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotated = rotate(arr)
print("Rotated Image")
for i in range(len(rotated)):
for j in range(len(rotated[0])):
print(rotated[i][j], end=" ")
print()Output:
Rotated Image
7 4 1
8 5 2
9 6 3
Time Complexity: O(N*N) to linearly iterate and put it into some other matrix.
Space Complexity: O(N*N) to copy it into some other matrix.
Solution 2: Optimized approach
Intuition: By observation, we see that the first column of the original matrix is the reverse of the first row of the rotated matrix, so that’s why we transpose the matrix and then reverse each row, and since we are making changes in the matrix itself space complexity gets reduced to O(1).
Approach:
Step 1: Transpose the matrix. (transposing means changing columns to rows and rows to columns)
Step 2: Reverse each row of the matrix.
Code:
C++ 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";
}
}Output:
Rotated Image
7 4 1
8 5 2
9 6 3
Time Complexity: O(N*N) + O(N*N).One O(N*N) is for transposing the matrix and the other is for reversing the matrix.
Space Complexity: O(1).
Java Code
import java.util.*;
class TUF {
static void rotate(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = i; j < matrix[0].length; j++) {
int temp = 0;
temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length / 2; j++) {
int temp = 0;
temp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length - 1 - j];
matrix[i][matrix.length - 1 - j] = temp;
}
}
}
public static void main(String args[]) {
int arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
rotate(arr);
System.out.println("Rotated Image");
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}Output:
Rotated Image
7 4 1
8 5 2
9 6 3
Time Complexity: O(N*N) + O(N*N).One O(N*N) is for transposing the matrix and the other is for reversing the matrix.
Space Complexity: O(1).
Python Code
from typing import List
def rotate(matrix: List[List[int]]) -> None:
n = len(matrix)
# transposing the matrix
for i in range(n):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# reversing each row of the matrix
for i in range(n):
matrix[i].reverse()
if __name__ == "__main__":
arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate(arr)
print("Rotated Image")
for i in range(len(arr)):
for j in range(len(arr[0])):
print(arr[i][j], end=" ")
print()Output:
Rotated Image
7 4 1
8 5 2
9 6 3
Time Complexity: O(N*N) + O(N*N).One O(N*N) is for transposing the matrix and the other is for reversing the matrix.
Space Complexity: O(1).
Special thanks to Pranav Padawe and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article