Difficulty: Medium, Asked-in: Google, Facebook, Microsoft, Amazon, Morgan Stanley
Key takeaway: A famous matrix-based problem that can be solved in place using loop and properties of matrix.
Given an n x n square matrix, write a program to rotate matrix by 90 degrees in the anticlockwise direction. It is expected to rotate matrix in place. In other words, we have to perform rotation by modify the 2D matrix directly.
Examples
Important note: Before moving on to solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!
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. For example:
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.
int[][] rotateMatrix(int X[][], int n)
{
int temp[n][n]
for (int i = 0; i < n; i = i + 1)
{
for (int j = 0; j < n; j = j + 1)
{
temp[n - j - 1][i] = X[i][j]
}
}
return temp
}
In the above approach, we are traversing input matrix using two nested loops which takes O(n²) time. So time complexity = O(n²). We are using an extra matrix takes of size n x n, so space complexity = O(n²).
As given in the problem description, can we solve problem without using extra space or in-place? Can we observe some pattern in the anticlockwise rotation of matrix? Let's think!
If we deep dive into the input and output matrices, we can find patterns to rotate matrix by swapping values. Let’s go through the same observation from above approach.
After the rotation of a matrix by 90 degrees anticlockwise:
So if we take the transpose of input matrix:
So one solution idea would be: If we take the transpose of input matrix and reverse each column, we will get the desired matrix rotated by 90 degrees in an anticlockwise direction (Think!)
Convert given matrix into its transpose : A transpose of a matrix is a matrix flipped over its diagonal, i.e., the row index of an element becomes the column index and vice versa. So, we need to swap elements at position X[i][j] with the element at X[j][i].
for (int i = 0; i < n; i = i + 1)
{
for (int j = i; j < n; j = j + 1)
{
swap(X[i][j], X[j][i])
}
}
Reverse the transposed matrix column-wise: We run two nested loops where outer loop scans each column from 0 to n - 1 and inner loop reverses each column by swapping values.
int i = 0, j = 0, column = 0
while (column < n)
{
i = 0, j = n - 1
while (i < j)
{
swap(X[i][column], X[j][column])
i = i + 1
j = j - 1
}
column = column + 1
}
void rotateMatrix(int X[][], int n)
{
if(n == 0 || n == 1)
return
for (int i = 0; i < n; i = i + 1)
{
for (int j = i; j < n; j = j + 1)
{
swap(X[j][i], X[i][j])
}
}
int i = 0, j = 0, column = 0
while (column < n)
{
i = 0, j = n - 1
while (i < j)
{
swap(X[i][column], X[j][column])
i = i + 1
j = j - 1
}
column = column + 1
}
}
We are traversing input matrix twice using nested loops. 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²). Space Complexity = O(1), as no extra memory is needed.
There is another idea that can solve this problem in place. If we track initial and final position of each element after the rotation, we can get a solution pattern.
So here are critical conservations for the solution:
void rotateMatrix(int X[][], int n)
{
for (int i = 0; i < n / 2; i = i + 1)
{
for (int j = i; j < n - i - 1; j = j + 1)
{
int temp = X[i][j]
X[i][j] = X[j][n - 1 - i]
X[j][n - 1 - i] = X[n - 1 - i][n - 1 - j]
X[n - 1 - i][n - 1 - j] = X[n - 1 - j][i]
X[n - 1 - j][i] = temp
}
}
}
We are traversing each element of the input matrix only once using a nested loop and fixing its correct position. Time complexity = O(n²). Space complexity = O(1), as no extra memory is needed.
Here is a precise mathematical analysis of the above code. For i = 0, inner loop is running n times, for i = 1, inner loop is running n - 2 times, for i = 2, inner loop is running n - 4 times, and so on! So total number of loop iterations = n + (n - 2) + (n - 4) + .... + 1 = 1 + 3 + 5 + .... + n - 4 + n - 2 + n (Note: This sequence is an arithmetic series, where last term will be 2 or 1 depending on whether n is even or odd. Suppose n is odd and the last term is 1)
The general formula of the sum of arithmetic series = n/2[2a + (n − 1) × d], where n is the total number of terms, a is the first term and d is a common difference. So in the sequence 1, 3, 5, ... n - 2, n, first term. = 1, total number of terms = n/2, common difference = 2.
If we put these values in the above formula of sum, total number of loop iterations = 1 + 3 + 5 + .... + n - 4 + n - 2 + n = n/4 [2 + (n/2 − 1) × 2] = n/4 [2 + (n/2 − 1) × 2] = n/4 * n = (n/2)^2. At each iteration, we are doing O(1) operations. So time complexity = Total number of loop iterations x O(1) = (n/2)^2 * O(1) = O(n^2)
Please write in the message below, if you find an error or you want to share more insights. Enjoy learning, Enjoy coding, Enjoy algorithms.
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.