Difficulty: Medium, Asked-in: Google, Facebook, Microsoft, Amazon, Morgan Stanley
Key takeaway: It is a famous matrix-based problem that can be solved in place using the loop and properties of the matrix.
Given an n x n square matrix, write a program to rotate it by 90 degrees in the anticlockwise direction. It is expected to rotate the matrix in place. Or in other words, we have to modify the input 2D matrix directly.
Examples
Important note: Before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!
If we observe input and output matrices, then the 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 according to the above observation.
The above algorithm uses traversal of the matrix using two nested loops which takes O(n²) time, and the use of an extra matrix takes O(n²) space. Hence, Time complexity = O(n²) and Space complexity = O(n²).
As given in the problem description, can we solve the problem without using extra space or in-place? Can we observe some pattern in the anticlockwise rotation of the matrix? Let's think!
If we deep dive into the input and output matrix, we can find patterns to rotate the matrix by swapping the values only. Let’s go through the same observation from the above approach. After the rotation of a matrix by 90 degrees anticlockwise:
So if we take the transpose of the input matrix, then:
If we compare the output matrix with the transpose of the input matrix, then the solution idea would be: if we take the transpose of the input matrix and reverse each column, we will get the desired matrix rotated by 90 degrees in an anticlockwise direction (Think!)
Convert the given matrix into its transpose : A transpose of a matrix is when the matrix is 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])
}
}
Then, reverse the transposed matrix column-wise: we run two nested loops where the outer loop scans each column from 0 to n-1 and the inner loop reverses each column by swapping the 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
}
We are traversing the 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 the initial and final position of each element after the rotation then we can get a solution pattern.
So here are the critical conservations for the solution:
We are traversing each element of the 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.
Thanks to Navtosh Kumar for his contribution in creating the first version of the content. Please write in the message below, if you find an error or you want to share more insights. Enjoy learning, Enjoy coding, Enjoy algorithms!
Given a 2-dimensional matrix, print the elements in spiral order. We can imagine the spiral traversal as an ordered set of matrix segments with horizontal and vertical boundaries, where both boundaries are reduced by one at each step. This is a good matrix problem to learn problem-solving using iteration and recursion.
Given a string S[], write a program to sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. If two characters have the same frequency, whichever occurs earliest in S, must come first. In other words, the sorting must be stable.
You are given an array of 1s and 0s and you are given an integer k which signifies the number of flips allowed. Write a program to find the position of zeros which when flipped will produce maximum continuous series of 1s.This is one of the good problems to understand the idea of the sliding window technique. Using this approach, We can solve several interview problems efficiently in O(n) and O(1) space.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.