Rotate Image
MedPrompt
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:
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]]
Constraints:
n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward approach but it violates the in-place requirement of the problem. It involves creating a new matrix of the same dimensions to store the rotated image and then copying the result back to the original matrix.
Algorithm
- Get the dimension
nof the matrix. - Create a new
n x ninteger matrix calledrotated. - Iterate through the original
matrixwith row indexifrom0ton-1and column indexjfrom0ton-1. - In each iteration, assign
matrix[i][j]torotated[j][n-1-i]. - After the loops complete, iterate through both matrices and copy the elements from
rotatedback tomatrix.
Walkthrough
The core idea is to map each element matrix[i][j] from the original matrix to its new position [j][n-1-i] in the rotated matrix.
- We first declare a new
n x nmatrix, sayrotated. - We then iterate through the original
matrixusing nested loops. For each elementmatrix[i][j], we calculate its new position and place it in therotatedmatrix:rotated[j][n-1-i] = matrix[i][j]. - After iterating through all elements, the
rotatedmatrix will contain the 90-degree clockwise rotated image. - Finally, we copy the contents of the
rotatedmatrix back into the originalmatrixto satisfy the function signature, although this doesn't make the algorithm in-place.
class Solution { public void rotate(int[][] matrix) { int n = matrix.length; int[][] rotated = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { rotated[j][n - 1 - i] = matrix[i][j]; } } // Copy the rotated matrix back to the original matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrix[i][j] = rotated[i][j]; } } }}Complexity
Time
O(n^2)
Space
O(n^2)
Trade-offs
Pros
Simple to understand and implement.
The logic for mapping coordinates is direct.
Cons
Violates the in-place constraint of the problem, making it an invalid solution for this specific problem statement.
High space complexity.
This approach rotates the matrix in-place by considering it as a set of concentric layers or shells. We rotate one layer at a time, starting from the outermost layer and moving inwards.
Algorithm
- Get the dimension
nof the matrix. - Iterate through the layers of the matrix. The outer loop runs from
i = 0ton/2 - 1. - For each layer
i, iterate through its elements. The inner loop runs fromj = iton - 1 - i - 1. - Inside the inner loop, perform a cyclic swap of four elements:
top = matrix[i][j]left = matrix[n-1-j][i]bottom = matrix[n-1-i][n-1-j]right = matrix[j][n-1-i]
- Use a temporary variable to store one element (e.g.,
top) and move the other three elements in a cycle:left -> top,bottom -> left,right -> bottom, and finallytemp -> right.
Walkthrough
An n x n matrix has floor(n/2) concentric layers. We can process each layer independently.
For each layer, we iterate through its elements and perform a cyclic swap of four elements at a time. Consider an element at matrix[row][col]. In a 90-degree clockwise rotation, it moves to matrix[col][n-1-row]. This element, in turn, moves to matrix[n-1-row][n-1-col], which moves to matrix[n-1-col][row], and finally, this last element moves back to the starting position matrix[row][col].
We can perform this 4-way swap using a single temporary variable. The outer loop iterates from the outermost layer (layer = 0) to the innermost one (layer < n/2). The inner loop iterates through the elements of the current layer, from the first element to the second-to-last element of a side (to avoid rotating corners multiple times).
class Solution { public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i < n / 2; i++) { for (int j = i; j < n - 1 - i; j++) { // Save the top element int temp = matrix[i][j]; // Move left to top matrix[i][j] = matrix[n - 1 - j][i]; // Move bottom to left matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; // Move right to bottom matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; // Move top to right matrix[j][n - 1 - i] = temp; } } }}Complexity
Time
O(n^2)
Space
O(1)
Trade-offs
Pros
Efficient in terms of space, satisfying the in-place requirement.
Performs the rotation in a single pass over the relevant elements.
Cons
The calculation of indices for the four-way swap can be tricky to get right and might be considered less intuitive than other in-place methods.
This is an elegant and efficient in-place approach that achieves the rotation by performing two simpler, sequential transformations: first transposing the matrix, and then reversing each row.
Algorithm
- Get the dimension
nof the matrix. - Transpose the matrix:
- Iterate with
ifrom0ton-1. - Iterate with
jfromi+1ton-1. - Swap
matrix[i][j]withmatrix[j][i].
- Iterate with
- Reverse each row:
- Iterate with
ifrom0ton-1(for each row). - Use two pointers,
left = 0andright = n-1. - While
left < right, swapmatrix[i][left]withmatrix[i][right], then incrementleftand decrementright.
- Iterate with
Walkthrough
A 90-degree clockwise rotation is mathematically equivalent to first transposing the matrix and then reversing each of its rows.
Step 1: Transpose the matrix. A transpose operation swaps matrix[i][j] with matrix[j][i]. To do this in-place, we can iterate through the upper triangle of the matrix (i.e., where j > i) and perform the swap.
Step 2: Reverse each row. After transposing, we iterate through each row of the modified matrix and reverse it. This can be done using a standard two-pointer technique for each row, swapping elements from the ends towards the center.
Combining these two steps results in the desired rotated matrix. This method is often preferred for its clarity and ease of implementation.
class Solution { public void rotate(int[][] matrix) { int n = matrix.length; // Step 1: Transpose the matrix for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } // Step 2: Reverse each row for (int i = 0; i < n; i++) { int left = 0; int right = n - 1; while (left < right) { int temp = matrix[i][left]; matrix[i][left] = matrix[i][right]; matrix[i][right] = temp; left++; right--; } } }}Complexity
Time
O(n^2)
Space
O(1)
Trade-offs
Pros
Very intuitive and easy to implement by breaking the problem into two standard matrix operations.
Code is clean and easy to read.
Satisfies the in-place O(1) space requirement.
Cons
Involves two passes over the data, which might be slightly less performant in theory than a single-pass approach, though the difference is usually negligible in practice.
Solutions
Solution
public class Solution { public void Rotate(int[][] matrix) { int n = matrix.Length; for (int i = 0; i < n >> 1; ++i) { for (int j = 0; j < n; ++j) { int t = matrix[i][j]; matrix[i][j] = matrix[n - i - 1][j]; matrix[n - i - 1][j] = t; } } for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { int t = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = t; } } }}public class Rotate_Image { public class Solution { /* eg: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 */ public void rotate ( int [][] m ) { // m for matrix if ( m == null || m . length == 0 ) { return ; } // for each circle, start position is (i,i), length is rectangle size // eg. above: (0,0), length=5; (1,1), length=3 int i = 0 ; int length = m . length ; while ( i < m . length / 2 ) { int count = 0 ; while ( count < length - 1 ) { // @note: extra attention here "-1". // while (count < length) { int tmp = m [ i ][ i + count ]; // i+length-1: last index of this rectangle // i+length-1 - count: index from backward m [ i ][ i + count ] = m [ i + length - 1 - count ][ i ]; m [ i + length - 1 - count ][ i ] = m [ i + length - 1 ][ i + length - 1 - count ]; m [ i + length - 1 ][ i + length - 1 - count ] = m [ i + count ][ i + length - 1 ]; m [ i + count ][ i + length - 1 ] = tmp ; count ++; } length -= 2 ; // @note: shrink each edge length by 2 i ++; // start point moving along diagonal } } } // An Inplace function to rotate a N x N matrix by 90 degrees in anti-clockwise direction static void rotateMatrix_anticlock ( int N , int mat [][]) { // Consider all squares one by one for ( int x = 0 ; x < N / 2 ; x ++) { // Consider elements in group of 4 in // current square for ( int y = x ; y < N - x - 1 ; y ++) { // store current cell in temp variable int temp = mat [ x ][ y ]; // move values from right to top mat [ x ][ y ] = mat [ y ][ N - 1 - x ]; // move values from bottom to right mat [ y ][ N - 1 - x ] = mat [ N - 1 - x ][ N - 1 - y ]; // move values from left to bottom mat [ N - 1 - x ][ N - 1 - y ] = mat [ N - 1 - y ][ x ]; // assign temp to left mat [ N - 1 - y ][ x ] = temp ; } } } static void rotateMatrix_clockwise ( int N , int mat [][]) { // Consider all squares one by one for ( int x = 0 ; x < N / 2 ; x ++) { // Consider elements in group of 4 in // current square for ( int y = x ; y < N - x - 1 ; y ++) { // store current cell in temp variable int temp = mat [ x ][ y ]; // move values from right to top mat [ x ][ y ] = mat [ y ][ N - 1 - x ]; // move values from bottom to right mat [ y ][ N - 1 - x ] = mat [ N - 1 - x ][ N - 1 - y ]; // move values from left to bottom mat [ N - 1 - x ][ N - 1 - y ] = mat [ N - 1 - y ][ x ]; // assign temp to left mat [ N - 1 - y ][ x ] = temp ; } } } } ////// class Solution_diagonal { public void rotate ( int [][] matrix ) { transpose ( matrix ); reflect ( matrix ); } public void transpose ( int [][] matrix ) { int n = matrix . length ; for ( int i = 0 ; i < n ; i ++) { for ( int j = i ; j < n ; j ++) { int tmp = matrix [ j ][ i ]; matrix [ j ][ i ] = matrix [ i ][ j ]; matrix [ i ][ j ] = tmp ; } } } public void reflect ( int [][] matrix ) { int n = matrix . length ; for ( int i = 0 ; i < n ; i ++) { for ( int j = 0 ; j < n / 2 ; j ++) { int tmp = matrix [ i ][ j ]; matrix [ i ][ j ] = matrix [ i ][ n - j - 1 ]; matrix [ i ][ n - j - 1 ] = tmp ; } } } } ////// class Solution { public void rotate ( int [][] matrix ) { int s = 0 , n = matrix . length ; while ( s < ( n >> 1 )) { int e = n - s - 1 ; for ( int i = s ; i < e ; ++ i ) { int t = matrix [ i ][ e ]; matrix [ i ][ e ] = matrix [ s ][ i ]; matrix [ s ][ i ] = matrix [ n - i - 1 ][ s ]; matrix [ n - i - 1 ][ s ] = matrix [ e ][ n - i - 1 ]; matrix [ e ][ n - i - 1 ] = t ; } ++ s ; } } }/** * @param {number[][]} matrix * @return {void} Do not return anything, modify matrix in-place instead. */ var rotate = function (matrix) { matrix.reverse(); for (let i = 0; i < matrix.length; i++) { for (let j = 0; j < i; j++) { [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]; } } };class Solution (object): def rotate(self, matrix): """ :type matrix: List[List[int]] :rtype: void Do not return anything, modify matrix in-place instead. """ if len(matrix) == 0: return h = len(matrix) w = len(matrix[0]) for i in range(0, h): # mirror for j in range ( 0 , w / 2 ): matrix [ i ][ j ], matrix [ i ][ w - j - 1 ] = matrix [ i ][ w - j - 1 ], matrix [ i ][ j ] for i in range ( 0 , h ): # transpos for j in range ( 0 , w - 1 - i ): matrix [ i ][ j ], matrix [ w - 1 - j ][ h - 1 - i ] = matrix [ w - 1 - j ][ h - 1 - i ], matrix [ i ][ j ] ############ class Solution : def rotate ( self , matrix : List [ List [ int ]]) -> None : n = len ( matrix ) for i in range ( n >> 1 ): for j in range ( n ): matrix [ i ][ j ], matrix [ n - i - 1 ][ j ] = matrix [ n - i - 1 ][ j ], matrix [ i ][ j ] for i in range ( n ): for j in range ( i ): matrix [ i ][ j ], matrix [ j ][ i ] = matrix [ j ][ i ], matrix [ i ][ j ]// OJ: https://leetcode.com/problems/rotate-image/ // Time: O(N^2) // Space: O(1) class Solution { public: void rotate ( vector < vector < int >>& A ) { int N = A . size (); for ( int i = 0 ; i < N / 2 ; ++ i ) { for ( int j = i ; j < N - i - 1 ; ++ j ) { int tmp = A [ i ][ j ]; A [ i ][ j ] = A [ N - j - 1 ][ i ]; A [ N - j - 1 ][ i ] = A [ N - i - 1 ][ N - j - 1 ]; A [ N - i - 1 ][ N - j - 1 ] = A [ j ][ N - i - 1 ]; A [ j ][ N - i - 1 ] = tmp ; } } } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.