Logicmojo - Updated Aug 28, 2021
Problem Statement: Matrix Rotation
matrix rotation: Given a matrix, rotate the matrix 90 degrees clockwise.
Matrix:
1 2 3
4 5 6
7 8 9
After rotation:
7 4 1
8 5 2
9 6 3
We have presented two approaches to find the two elements:
• Array in form of Squares• Transpose & Reverse
Approach 1: To solve the question without any extra space, rotate the array in form of squares, dividing the matrix into squares or cycles. For example, A 4 X 4 matrix will have 2 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. The idea is for each square cycle, swap the elements involved with the corresponding cell in the matrix in clockwise direction one at a time using nothing but a temporary variable to achieve this.
Algorithm:
1. There is N/2 squares or cycles in a matrix of side N. Process a square one at a time. Run a loop to traverse the matrix a cycle at a time, i.e loop from 0 to N/2 - 1, loop counter is i
2. Consider elements in group of 4 in current square, rotate the 4 elements at a time. So the number of such groups in a cycle is N - 2 * i.
3. So run a loop in each cycle from x to N - x - 1, loop counter is y
4. The elements in the current group is (x, y), (y, N-1-x), (N-1-x, N-1-y), (N-1-y, x), now rotate the these 4 elements, i.e (x, y) <- (y, N-1-x), (y, N-1-x)<- (N-1-x, N-1-y), (N-1-x, N-1-y)<- (N-1-y, x), (N-1-y, x)<- (x, y)
5. Print the matrix.
C++ Implementation:class Solution { public: void rotate(vector<vector<int>>& matrix) { int n=matrix.size(); for(int i=0;i<n/2;i++){ for(int j=i;j<=n-i-2;j++){ int temp=matrix[i][j]; matrix[i][j]=matrix[n-1-j][i]; matrix[n-1-j][i]=matrix[n-1-i][n-1-j]; matrix[n-1-i][n-1-j]=matrix[j][n-1-i]; matrix[j][n-1-i]=temp; } } } };
Python Implementation:
class Solution: def rotate(self, arr): """ Do not return anything, modify matrix in-place instead. """ n = len(arr) - 1 for i in range(len(arr)//2): for j in range(i, n - i): p1 = arr[i][j] p2 = arr[j][n - i] p3 = arr[n - i][n - j] p4 = arr[n - j][i] ##swapping arr[j][n - i] = p1 arr[n - i][n - j] = p2 arr[n - j][i] = p3 arr[i][j] = p4 ob1 = Solution() matrix = [[1,2,3],[4,5,6],[7,8,9]] print(ob1.rotate(matrix))
Time Complexity: O(n*n), where n is side of array. A single traversal of the matrix is needed.
Space Complexity: O(1)
Transpose & Reverse
For rotating the matrix is to firstly reverse the matrix around the main diagonal, and then reverse it from left to right. These operations are called transpose and reflect in linear algebra.
Time: O(n*n) + 0(n*n), where n is number of elements in the array nums.
Space: O(1)
C++ Implementation:
class Solution { public: void rotate(vector<vector<int>>& matrix) { for(int i=0; i<matrix.size(); i++) { for(int j=i; j<matrix[0].size(); j++) swap(matrix[i][j], matrix[j][i]); } for(int i=0; i<matrix.size(); i++) { for(int j=0, k=matrix[0].size()-1; j < k; j++, k--) swap(matrix[i][j], matrix[i][k]); } } };
Python Implementation:
class Solution: def rotate(self, matrix: List[List[int]]) -> None: // reverse matrix upside down matrix.reverse() // transpose elements on primary diagonal for i in range( len(matrix) ): for j in range(i): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
With this article at Logicmojo, you must have the complete idea of solving Matrix Rotation problem.