Given a square matrix (n * n), turn it by 90 degrees in a clockwise direction without using any extra space.
Input: 1 2 3 4 5 6 7 8 9 Output: 7 4 1 8 5 2 9 6 3
Solutions
Method 1: In O(n^2) time and O(n^2) space
In this approach, we use an auxiliarry matrix of size n * m (if the original matrix is m * n).
We can observe that the first row of the original matrix makes the last column of the rotated matrix, i.e., {0,0 -> 0,m-1}, {0,1 -> 1,m-1} . . . {i,j -> j,(m-1-i)}
We start by traversing the original matrix row by row and putting matrix[i][j] in tmp[j][(m - 1) - i].
Note: This solution also works if the matrix is not a square, i.e., n != m.
Complexity
The time complexity of this solution is O(n^2) and space complexity is O(n^2).
Method 2: In O(n^2) time and O(1) space
We can observe that the first column of the original matrix makes up the first row of the rotated matrix in reverse order.
To achieve this, we transpose the matrix and then reverse each row, all in the same matrix to keep the space complexity O(1).
In order to transpose a matrix, we start by traversing it row by row and converting each row into a column and each column into a row.
While traversing, make sure to visit each element only once, i.e., j = i+1.
Complexity
The time complexity of this solution is O(n^2) and space complexity is O(1).