When writing a rotation matrix or a rotation-translation matrix parameters out as a list, specify the order (rows-first or columns-first).When working with rotation matrix decompositions, specify the handedness of the rotation.Specify if the meaning is a rotation/translation of points or a rotation/translation of axes.Element at position (n - 1 - i, n - 1 - j) will go to position (n - 1 - j, i).Let \(\mathbf\right]\) Key Considerations.Element at position (j, n - 1 - i) will go to position (n - 1 - i, n - 1 - j).Element at position (i, j) will go to position (j, n - 1 - i).Element at position (n - 1 - j, i) will go to position (i, j).So we rotate these four elements by 90 degrees in anticlockwise order: In general, position of elements in the any cycle is: (n - 1 - j, i), (i, j), (j, n - 1 - i) and (n - 1 - i, n - 1 - j). We swap elements involved in each cycle in anticlockwise direction, i.e., from right to top, top to left, left to bottom, and bottom to right. In each square, elements are moved in a cycle of 4 elements.And so on, we move from the outer square to innermost square. Then we process the second square formed by second row, second-last column, second-last row, and second column. So, we can process each square one at a time using a nested loop. We first process the first square formed by first row, last column, last row, and first column. There is total n/2 squares in a n*n matrix.
So here are critical conservations for the solution: If we track initial and final position of each element after the rotation, we can get a solution pattern. There is another idea that can solve this problem in place. An efficient approach using nested loops (In-place) Solution Idea and Steps Space Complexity = O(1), as no extra memory is needed. Time complexity = Time complexity of converting input matrix into a transpose + Time complexity of reversing transposed matrix column-wise = O(n²) + O(n²) = O(n²). We are traversing input matrix twice using nested loops. Int rotateMatrix ( int X, int n ) Time and space complexity analysis The last row of input matrix = The last column of output matrix in reverse order.The second row of input matrix = The second column of output matrix in reverse order and so on.The first row of input matrix = The first column of output matrix in reverse order.So one basic idea would be to use an extra matrix of the same size and directly copy elements from the original matrix based on above observation. The first column in output matrix: 4, 3, 2, 1.The first row in input matrix: 1, 2, 3, 4,.If we observe input and output matrices, following pattern would be visible: The first row has turned into the first column in reverse order. Similarly, second, third, …rows have turned into their respective column in reverse order. An efficient approach using nested loops (In-place)Ī brute force approach using extra space Solution Idea and Steps.An efficient approach using the transpose of the matrix.Enjoy problem-solving! Discussed solution approaches Important note: Before moving on to solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. In other words, we have to perform rotation by modify the 2D matrix directly. It is expected to rotate matrix in place. Given an n x n square matrix, write a program to rotate matrix by 90 degrees in the anticlockwise direction. Key takeaway: A famous matrix-based problem that can be solved in place using loop and properties of matrix. Difficulty: Medium, Asked-in: Google, Facebook, Microsoft, Amazon, Morgan Stanley
0 kommentar(er)
