Description:
You are given an n x n 2D matrix representing an image, rotate the image 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.
Examples:
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:
Input: matrix = [[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]]Solution in Python:
To solve the problem of rotating a 2D matrix by 90 degrees in-place, we can follow a two-step approach:
- Transpose the matrix.
- Reverse each row.
Python
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Rotate the matrix in-place by 90 degrees clockwise.
"""
n = len(matrix)
# Step 1: Transpose the matrix.
# Transposing means converting rows to columns and vice versa.
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Step 2: Reverse each row.
# Reversing each row of the transposed matrix gives us the desired rotation.
for i in range(n):
matrix[i].reverse()Explanation:
- Transpose the Matrix:
- Transposing involves swapping the element at position
(i, j)with the element at position(j, i). - We iterate over the upper triangle of the matrix (including the diagonal) to perform the swaps, thus transforming rows into columns.
- Transposing involves swapping the element at position
- Reverse Each Row:
- After transposing, each row is reversed. This step effectively completes the 90-degree rotation.
- Reversing each row can be done using the
reverse()method in Python.
By following these two steps, the matrix is rotated 90 degrees in-place without using any additional space for another matrix. This approach ensures that the operation is performed efficiently with a time complexity of O(n^2).
Solution in Javascript:
JavaScript
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function(matrix) {
const n = matrix.length;
// Step 1: Transpose the matrix.
// Transposing means converting rows to columns and vice versa.
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
// Swap element at (i, j) with element at (j, i)
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
// Step 2: Reverse each row.
// Reversing each row of the transposed matrix gives us the desired rotation.
for (let i = 0; i < n; i++) {
matrix[i].reverse();
}
};Solution in Java:
Java
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// Step 1: Transpose the matrix.
// Transposing means converting rows to columns and vice versa.
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// Swap element at (i, j) with element at (j, i)
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// Step 2: Reverse each row.
// Reversing each row of the transposed matrix gives us the desired rotation.
for (int i = 0; i < n; i++) {
int left = 0, right = n - 1;
while (left < right) {
// Swap elements at (i, left) and (i, right)
int temp = matrix[i][left];
matrix[i][left] = matrix[i][right];
matrix[i][right] = temp;
left++;
right--;
}
}
}
}Solution in C#:
C#
public class Solution {
public void Rotate(int[][] matrix) {
int n = matrix.Length;
// Step 1: Transpose the matrix.
// Transposing means converting rows to columns and vice versa.
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// Swap element at (i, j) with element at (j, i)
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// Step 2: Reverse each row.
// Reversing each row of the transposed matrix gives us the desired rotation.
for (int i = 0; i < n; i++) {
Array.Reverse(matrix[i]);
}
}
}