48. Rotate Image - Detailed Explanation
Problem Statement
You are given an n x n 2D matrix representing an image, and you need to rotate the image by 90 degrees clockwise. The rotation must be done in-place, meaning you should modify the input matrix directly without using an additional matrix for the rotation.
-
Constraints:
n == matrix.length == matrix[i].length(the matrix is square)1 <= n <= 20(size of matrix)-1000 <= matrix[i][j] <= 1000(range of matrix element values)
-
Goal: After rotation, element values that were originally on the top row should end up on the rightmost column, the rightmost column should become the bottom row, and so on, forming the rotated matrix.
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]]
Explanation: In this 4×4 example, each row of the original matrix becomes a column of the rotated matrix. For instance, the top row [5,1,9,11] becomes the rightmost column of the output, and the leftmost column of the original [5,2,13,15] becomes the bottom row [15,14,12,16] of the rotated matrix. The 90° rotation thus shifts every element to its new position in a clockwise direction.
Hints
-
Think in Terms of Coordinates: Try mapping the index of one element to its new index after a 90° rotation. For an element at position
(i, j), where does it move? (Hint: it should end up at(j, n-1-i)for a clockwise rotation .) Recognizing this mapping is key to solving the problem. -
Use Extra Space Conceptually: If in-place rotation seems tricky, first imagine using an extra matrix to place each element directly into its rotated position. This can clarify how elements move. Once you understand this, you can translate it into an in-place method.
-
Leverage Matrix Operations: Notice that a 90° clockwise rotation can be achieved by simple transformations: for example, transposing the matrix and then reversing each row will rotate the matrix clockwise. Likewise, flipping the matrix upside-down then transposing it also works. Breaking the task into these steps might make the in-place solution more approachable.
Multiple Approaches with Code
Approach 1: Brute Force (Using an Auxiliary Matrix)
Detailed Explanation: This straightforward approach uses an extra matrix to build the rotated result. We create a new matrix of the same size, then copy each element from the original to its correct rotated position. Specifically, the element at position (i, j) in the original matrix will move to position (j, n-1-i) in the rotated matrix. After filling the new matrix, we copy it back to the original matrix (to simulate in-place modification).
Steps to implement:
- Initialize a new
n x nmatrix (let's call itrotated) filled with zeros. - Loop over each cell
(i, j)of the original matrix. Place the valuematrix[i][j]intorotated[j][n-1-i]. This moves the top row to the rightmost column, the left column to the top row, and so forth. - Copy all values from
rotatedback intomatrix(since the problem expects the original matrix to be modified in-place).
This approach is easy to understand, but it uses O(n²) extra space for the auxiliary matrix, which violates the "in-place" requirement. It's useful for conceptual understanding and verifying the rotation logic.
Python Code Implementation:
Java Code Implementation:
Approach 2: In-Place Rotation (Transpose then Reverse Rows)
Detailed Explanation: This approach performs the rotation in two in-place steps without needing extra space: transpose the matrix, then reverse each row.
- Transpose: Swapping
matrix[i][j]withmatrix[j][i]for alli < jconverts rows into columns and vice versa. After transposing, the original top row becomes the leftmost column. For example, transposing[[1,2,3],[4,5,6],[7,8,9]]results in[[1,4,7],[2,5,8],[3,6,9]]. - Reverse Rows: After transposition, reversing each row (swap the elements symmetrically across the middle of the row) will complete the 90° clockwise rotation. Continuing the example, reversing each row of
[[1,4,7],[2,5,8],[3,6,9]]yields[[7,4,1],[8,5,2],[9,6,3]], which is the final rotated matrix.
Why does this work? Rotating clockwise can be seen as first reflecting the matrix over its main diagonal (that’s the transpose step) and then reflecting it vertically (reversing rows). This combination achieves the same result as a single 90° clockwise rotation. The process is in-place because swapping elements for transpose and reversing rows can be done within the original matrix memory.
Steps to implement:
- Transpose the matrix: Loop through the matrix and swap element
(i, j)with(j, i)for all0 <= i < nandi < j < n. This converts the matrix’s rows into columns. - Reverse each row: For each row, swap the elements symmetrically from the ends moving toward the center (i.e., swap element at index
jwith element at indexn-1-jforjfrom 0 to⌊(n-1)/2⌋). This flips the matrix horizontally, completing the clockwise rotation.
This approach uses O(1) extra space (in-place swaps) and runs in O(n²) time.
Python Code Implementation:
Java Code Implementation:
Note: Instead of transposing then reversing rows, you could also rotate by reversing the columns first and then transposing – this is an equivalent procedure. The choice of row-reversal vs. column-reversal depends on the direction of rotation (for counter-clockwise rotation, you'd transpose then reverse columns instead of rows).
Approach 3: Optimized In-Place Rotation (Layer-by-Layer Swapping)
Detailed Explanation: This method rotates the matrix in place by swapping four elements at a time, one from each side of the matrix. The idea is to perform the rotation layer by layer (or ring by ring). The outermost layer of the matrix will be rotated, then the next inner layer, and so on. For each layer, we swap the four corresponding elements (top, right, bottom, left) that are in the positions of a 90° rotation cycle.
Consider the matrix indices for an element in the position (i, j) in the top row of a given layer:
- The element at
(i, j)moves to the right side at(j, n-1-i). - The element at
(j, n-1-i)(right side) moves to the bottom at(n-1-i, n-1-j). - The element at
(n-1-i, n-1-j)(bottom) moves to the left side at(n-1-j, i). - The element at
(n-1-j, i)(left side) moves to the top at(i, j).
By doing these four moves simultaneously (with the help of a temporary variable to hold one value), we rotate those four cells. We repeat this for every position in the current layer (except the last element of each side, which gets handled by earlier swaps in the loop) and then move inward to the next layer.
For a matrix of size n, there are ⌊n/2⌋ layers (each layer is a concentric square). Within each layer i, we iterate j from i to n-1-i-1 (inclusive) to rotate all elements in that layer. Using this method, each element is moved directly to its final position in one pass.
Steps to implement for each layer i:
- Iterate
jfromiton - 1 - i - 1. For eachj:- Save the top element
temp = matrix[i][j]. - Move left element to top:
matrix[i][j] = matrix[n-1-j][i]. - Move bottom element to left:
matrix[n-1-j][i] = matrix[n-1-i][n-1-j]. - Move right element to bottom:
matrix[n-1-i][n-1-j] = matrix[j][n-1-i]. - Move
temp(original top) to right:matrix[j][n-1-i] = temp.
- Save the top element
- Repeat for the next element in the layer until the layer is complete, then proceed to the next inner layer.
This approach also runs in O(n²) time and uses O(1) space. It is considered more "optimized" in the sense that it completes the rotation in a single pass through the matrix (and is a classic in-place algorithm for rotation). However, the complexity is the same as the transpose-and-reverse method; the main difference is in constant factors and the style of implementation.
Python Code Implementation:
Java Code Implementation:
Complexity Analysis
For each approach, let n be the number of rows (and columns) of the matrix:
- Brute Force (Auxiliary Matrix): Time Complexity = O(n²) because we traverse all n² elements to fill the new matrix. Space Complexity = O(n²) extra, due to the auxiliary matrix of the same size as input.
- Transpose + Reverse (In-Place): Time Complexity = O(n²). Transposing takes ~n²/2 swaps and reversing rows takes ~n²/2 swaps, which is overall O(n²) operations. Space Complexity = O(1) extra, since all modifications are done in place using constant temp storage for swaps.
- Layer-by-Layer Swapping (In-Place): Time Complexity = O(n²). We still move each of the n² elements once; it's just done in a single nested loop pass. Space Complexity = O(1), using only a temporary variable for swaps.
All approaches have the same asymptotic time complexity, but the in-place methods are more space-efficient than the brute force method (which uses additional memory). In practice, the two-step transpose method and the direct layer-by-layer method are both efficient for the given constraints and n up to 20 (even for larger n, O(n²) is acceptable since the number of operations grows quadratically with the matrix side length).
Common Mistakes
-
Rotating in the Wrong Direction: It’s easy to accidentally rotate counter-clockwise instead of clockwise (or vice versa). Remember that for a clockwise rotation, element
(i,j)should go to(j, n-1-i). If you swap the wrong indices (for example,(i,j)->(n-1-j, i)), you’ll end up with a 90° counter-clockwise rotation or a completely wrong result. Double-check the index mapping for correctness. -
Overwriting Values In-Place: When doing the in-place layer-by-layer swap, a common mistake is to overwrite a value before it’s been moved to its correct position. Always use a temporary variable to hold one of the values during the four-way swap, so you don’t lose it. Each cycle of four swaps should use one temp variable to safely rotate the four values.
-
Incorrect Loop Bounds: Getting the loop ranges right is tricky. Off-by-one errors can cause index out-of-bounds or leave out the last element in a layer. For the layer-by-layer approach, ensure that
jruns fromiton-1-i-1(inclusive). For the transpose step, make sure to only swap elements wherej > i(ori < j) to avoid swapping back again. -
Not Handling Small Matrices: Forgetting to handle the smallest cases can cause issues. For example, a 1x1 matrix should remain unchanged (your loops should naturally handle this by doing zero iterations, but make sure they do). A 2x2 matrix is a simple case to manually verify your logic (it should swap the four cells accordingly).
-
Using Extra Space Unnecessarily: After understanding the problem, some might still use an extra matrix out of habit. Remember that the challenge specifically asks for an in-place solution. Using extra space might pass for correctness but would not meet the optimal criteria. Practice the in-place method once you grasp the concept with extra space.
Edge Cases
-
1x1 Matrix: A single-element matrix should remain the same after rotation. Ensure your code can handle
n=1without issues (it should, as the loops will either not run or just transpose the only element with itself). -
Even and Odd Dimensions: Make sure your solution works for both even-sized matrices (e.g., 2x2, 4x4) and odd-sized matrices (e.g., 3x3, 5x5). For odd
n, the center element of the matrix stays in place during rotation, and the layer-by-layer approach should naturally leave it untouched. -
Negative or Duplicate Values: The values themselves don't affect the rotation logic. However, using distinct numbers in testing (like the examples) makes it easier to verify that each element moves to the correct position. If all values are the same, the matrix looks unchanged after rotation (which is a trivial correct outcome).
-
Maximum Size: Although the constraint here is
n <= 20, ensure your algorithm would work for largernas well (in terms of logic and not using too much extra space). The in-place methods are efficient and would scale to larger matrices if needed (with runtime increasing quadratically).
Alternative Variations
- Rotate 90° Counter-Clockwise: A similar problem is to rotate the matrix 90 degrees anti-clockwise. This can be done in-place by transposing and then reversing each column (instead of each row), or by doing three clockwise rotations. The logic is symmetrical – for counter-clockwise, element
(i,j)would move to(n-1-j, i). - Rotate by 180°: Rotating by 180 degrees (clockwise or anti-clockwise yields the same result) will turn the matrix upside down. This can be done by swapping elements in two steps or by applying the 90° rotation twice. In-place, you can swap
(i,j)with(n-1-i, n-1-j)for all applicable pairs. This is simpler since it's just two-way swaps. - Non-Square Matrix Rotation: The 90° rotation is typically defined for square matrices (so that the result has the same dimensions). If you have a non-square matrix (m x n), a 90° rotation will produce an n x m matrix. That scenario cannot be done in-place in the same array, but you could create a new matrix of size n x m and fill it accordingly. (This is a different problem variant because in-place rotation is only possible when the matrix is square.)
- Multiple Rotations: Sometimes you might be asked to rotate by 270° clockwise (which is the same as 90° counter-clockwise) or other multiples of 90. You can always reduce the problem: e.g., 270° clockwise = 90° clockwise done three times. However, it’s more efficient to directly apply the appropriate transformation (transpose + flip in the correct orientation, or use the layer swap method adjusted for that angle).
- Layer Rotation in Other Contexts: The layer-by-layer swapping technique can be adapted to other problems, such as rotating elements in a matrix by k positions, or rotating only the border of a matrix. Understanding the index manipulation in this problem sets a foundation for those variations.
Related Problems for Further Practice
- Transpose Matrix (LeetCode 867) – Easy problem of transposing a 2D matrix. This is a sub-step of the rotation logic and helps reinforce understanding of swapping indices.
- Image Flip (LeetCode 832) – Flip an image horizontally and invert it (related to reversing rows, similar concept of transforming matrix in-place).
- Rotate Array (LeetCode 189) – Rotate a 1D array to the right by k steps. Although one-dimensional, in-place rotation techniques (using reversal or cyclic swaps) are analogous to this 2D problem.
- Spiral Matrix (LeetCode 54) – Traverse a matrix in spiral order. This involves moving layer by layer around a matrix (conceptually related to the layering idea in rotation).
- Spiral Matrix II (LeetCode 59) – Generate an n x n matrix filled with numbers 1 to n² in spiral order. Again involves layer-wise filling, which is akin to layer-wise reading or rotation.
- Set Matrix Zeroes (LeetCode 73) – Although a different problem (setting entire rows/columns to zero), it requires careful in-place matrix manipulation, which is good practice for thinking about index transformations and avoiding extra space.
By practicing these related problems, you can strengthen your understanding of matrix manipulations, in-place algorithms, and index transformations — all of which are exemplified in the Rotate Image problem. Good luck!
GET YOUR FREE
Coding Questions Catalog
