Rotate Image
Problem Description
If you are given an n x n 2D matrix representing an image, rotate it by 90 degrees (clockwise). You have to rotate the image in place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
The rotation must be done in place, meaning you have to modify the given matrix directly without allocating extra space for another matrix.
Examples
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Explanation: Performing rotation in the given matrix
1 2 3 7 4 1
4 5 6 —> 8 5 2
7 8 9 9 6 3
Input: [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Explanation: Performing rotation in the given matrix
5 1 9 11 15 13 2 5
2 4 8 10 —> 14 3 4 1
13 3 6 7 12 6 8 9
15 14 12 16 16 7 10 11
Constraints
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000
Intuition
Imagine you have a square grid, like a tic-tac-toe board, but larger. Each cell in this grid contains a number, and our goal is to rotate this grid by 90 degrees clockwise, like turning a picture frame. We want to achieve this without creating a new grid, meaning we need to rotate it in place—just by manipulating the original matrix.
The key idea is to understand how the elements in the matrix change their positions during a 90-degree rotation.
Take a 3x3 matrix for example:
Notice how:
The element at the top-left corner (1) ends up in the top-right corner. The element in the top-right (3) moves to the bottom-right. The element in the bottom-right (9) moves to the bottom-left.
Looking at the entire grid, we see a pattern: each element’s row and column positions are rearranged to achieve the rotation.
- The first column of the original matrix, [1,4,7], has become the first row of the rotated matrix but in a reversed order: [7,4,1].
- The second row, [2,5,8], has become the middle row but in a reverse order: [8,5,2].
- Similarly, the third column, [9,6,3], has become the third column but in reverse order: [9,6,3].
In essence, rows turn into columns, and the order of elements within those rows is flipped.
This gives us a hint: rotating the matrix involves two key transformations. First, convert every column into a row. Then, reverse the order of elements in each row. These steps together produce the desired rotation.
Transpose of the matrix: Transposing a matrix means converting its rows into columns. This way, the diagonal remains the same, but all other elements are swapped.
For example, after transposing the 3x3 matrix, it looks like this:
Each element [i][j] gets swapped with [j][i], which moves it to the correct row for rotation.
Reverse each row: Once transposed, reversing each row gives us the final 90-degree clockwise rotation.
Reversing the rows results in:
So, the overall approach would be, to transpose the matrix to shift elements from rows to columns and Reverse each row to achieve the rotation effect.
Let Understand it with the dry-run
Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Step 1: Transpose the Matrix
- Initial: matrix[0][1] = 2 swaps with matrix[1][0] = 4
- Result: matrix[0][1] = 4, matrix[1][0] = 2
- Next: matrix[0][2] = 3 swaps with matrix[2][0] = 7
- Result: matrix[0][2] = 7, matrix[2][0] = 3
- Final Transpose: matrix[1][2] = 6 swaps with matrix[2][1] = 8
- Result: matrix[1][2] = 8, matrix[2][1] = 6
Step 2: Reverse Each Row
- Row 1: [1, 4, 7] becomes [7, 4, 1]
- Row 2: [2, 5, 8] becomes [8, 5, 2]
- Row 3: [3, 6, 9] becomes [9, 6, 3]
Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
Let's visualize it for a better understanding
Code Implementation
C++ Code Try on Compiler!
class Solution {
public:
// Function to rotate the matrix by 90 degrees clockwise
void rotate(vector<vector<int>>& matrix) {
// First step: Transpose the matrix
for (int i = 0; i < matrix.size(); i++) {
for (int j = i + 1; j < matrix[0].size(); j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
// Second step: Reverse each row
for (int i = 0; i < matrix.size(); i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
}
};Java Code Try on Compiler!
class Solution {
// Function to rotate the matrix by 90 degrees clockwise
public void rotate(int[][] matrix) {
// First step: Transpose the matrix
for (int i = 0; i < matrix.length; i++) {
for (int j = i + 1; j < matrix[0].length; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// Second step: Reverse each row
for (int i = 0; i < matrix.length; i++) {
int[] row = matrix[i];
for (int j = 0; j < row.length / 2; j++) {
int temp = row[j];
row[j] = row[row.length - j - 1];
row[row.length - j - 1] = temp;
}
}
}
}Python Code Try on Compiler!
class Solution:
# Function to rotate the matrix by 90 degrees clockwise
def rotate(self, matrix):
# First step: Transpose the matrix
for i in range(len(matrix)):
for j in range(i + 1, len(matrix[0])):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Second step: Reverse each row
for i in range(len(matrix)):
matrix[i].reverse()Javascript Code Try on Compiler!
class Solution {
// Function to rotate the matrix by 90 degrees clockwise
rotate(matrix) {
// First step: Transpose the matrix
for (let i = 0; i < matrix.length; i++) {
for (let j = i + 1; j < matrix[0].length; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
// Second step: Reverse each row
for (let i = 0; i < matrix.length; i++) {
matrix[i].reverse();
}
}
}Time Complexity : O(n²)
The time complexity of the matrix rotation algorithm is determined by two main operations: transposing the matrix and reversing each row.
Transposing Operations
Transposing involves iterating through the upper triangular part of the matrix and swapping elements above the diagonal, resulting in n*(n - 1)/2 swaps. Since this operation involves iterating over all pairs of elements for i < j, it takes O(n²) time.
Reverse Operations
After transposing, the algorithm proceeds to reverse each row, which takes linear time, O(n), per row. Given that there are n rows, this step also results in a time complexity of O(n²).
Therefore, the overall time complexity of the algorithm is O(n²), where n is the size of the matrix.
Space Complexity : O(n²)
Now let’s evaluate the space complexity of this solution, taking into account both the total space used and the auxiliary space.
Auxiliary Space Complexity
Explanation: The auxiliary space refers to any extra space used by the algorithm aside from the input matrix. In this case, the algorithm only uses a few temporary variables for swapping matrix elements, and no new arrays or data structures are allocated. Therefore, the auxiliary space complexity is O(1), meaning the algorithm uses constant extra space.
Total Space Complexity
Explanation: The total space used by the algorithm is determined by the matrix itself, which is modified in place. The matrix size is n x n, and no extra matrix or data structures are created during the process.
Thus, the space used by the input matrix remains constant as O(n²), but since it is not additional space beyond the input, it doesn't contribute to the overall space complexity.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an m x n matrix, return all elements of the matrix in spiral order.
You are given an m x n matrix of characters box representing a side-view of a box. Each cell of the box is one of the following:
- A stone '#'
- A stationary obstacle '*'
- Empty '.'
The box is rotated 90 degrees clockwise, causing some of the stones to fall due to gravity. Each stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity does not affect the obstacles' positions, and the inertia from the box's rotation does not affect the stones' horizontal positions.
It is guaranteed that each stone in box rests on an obstacle, another stone, or the bottom of the box.
Return an n x m matrix representing the box after the rotation described above.