Rotate Image
Problem 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.
Example 1:
Example 2:
Output:
Constraints:
- n == matrix.length == matrix[i].length
- 1 <= n <= 20
- -1000 <= matrix[i][j] <= 1000
Solve it on LeetCode
Approaches
1. Brute Force with Extra Space
Intuition:
To rotate a matrix clockwise by 90 degrees, we can utilize an auxiliary matrix. The idea is to iterate through each element of the matrix and place it appropriately in the new matrix. Specifically, each element at position (i, j) in the original matrix will be placed at position (j, n-1-i) in the rotated matrix.
Steps:
- Create an auxiliary matrix of the same size as the input matrix.
- For each element in the original matrix, calculate its new position in the auxiliary matrix using the formula:
rotated[j][n-1-i] = original[i][j]. - Copy the rotated matrix back to the original matrix.
Code:
- Time Complexity: O(n^2), where
nis the number of rows (or columns) in the matrix. - Space Complexity: O(n^2) for the auxiliary matrix.
2. In-Place Transpose and Reverse
Intuition:
A more efficient solution is to perform the transformation in place by first transposing the matrix (flipping it over its diagonal) and then reversing each row. Transposing by itself will reorder the elements diagonally, while reversing will yield the required 90-degree clockwise rotation.
Steps:
- Transpose the Matrix: Swap each element
(i, j)with the element(j, i). - Reverse Each Row: For each row in the transposed matrix, reverse the elements of the row.
Code:
- Time Complexity: O(n^2), where
nis the number of rows (or columns) in the matrix. - Space Complexity: O(1), since we are doing the operations in place without using extra space.