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] <= 1000Problem Overview: You are given an n x n matrix representing an image. The task is to rotate the matrix 90 degrees clockwise in-place. No extra matrix is allowed, so every value must be repositioned within the same structure.
The problem is essentially a coordinate transformation inside a square matrix. A value at position (r, c) moves to (c, n - 1 - r) after a 90° clockwise rotation. Implementing this efficiently requires rearranging elements without overwriting values.
Approach 1: Transpose and Reverse (O(n²) time, O(1) space)
This method breaks rotation into two deterministic operations on the array-backed matrix. First, transpose the matrix by swapping matrix[i][j] with matrix[j][i] for all i < j. Transposition flips the matrix along its main diagonal, converting rows into columns. After that, reverse each row of the matrix. Reversing the rows shifts elements to their final rotated positions. Both steps iterate through the matrix once, resulting in O(n²) time while keeping space usage O(1) because swaps happen in-place.
The key insight is recognizing that a clockwise rotation equals transpose + horizontal reflection. This approach is clean, easy to implement, and avoids complex index calculations.
Approach 2: Layer by Layer Rotation (O(n²) time, O(1) space)
This approach treats the matrix like concentric square layers. Start from the outer layer and move inward. For each layer, iterate through the elements along the top edge and rotate four corresponding positions at a time: top → right → bottom → left → top. Each iteration performs a four-way swap using a temporary variable.
For example, an element at the top row moves to the right column, the right column moves to the bottom row, the bottom row moves to the left column, and the left column moves back to the top. The process repeats for every element in the current layer before moving inward. Since every element is moved exactly once, the total runtime remains O(n²) with constant O(1) space.
This method relies heavily on index arithmetic and understanding how coordinates shift during rotation. It directly simulates the geometric rotation rather than decomposing it into matrix operations.
Recommended for interviews: The transpose-and-reverse approach is usually what interviewers expect because it demonstrates pattern recognition in matrix transformations. The layer-by-layer method shows deeper understanding of index manipulation and in-place rotation mechanics. Knowing both helps you explain the math behind the transformation and implement the cleaner solution quickly.
This approach utilizes two main operations. First, we transpose the matrix, which means flipping it over its diagonal. In other words, swap matrix[i][j] with matrix[j][i]. After transposing the matrix, we reverse each row. This combination results in a 90-degree clockwise rotation.
The code first transposes the given matrix in place using two nested loops. Then, for each row, it reverses the elements to achieve a 90-degree clockwise rotation.
Time Complexity: O(n^2) - Because we loop through each element once.
Space Complexity: O(1) - No extra space is used, operations are in-place.
This approach rotates the matrix layer by layer or ring by ring. Start from the outer layer and move to the inner layer, rotating elements by moving them in groups of four. This involves swapping the elements in four-step rotations.
The C solution processes the matrix in concentric layers, shifting each element appropriately to its new position during the 90-degree rotation.
Time Complexity: O(n^2) - Each individual element is moved once.
Space Complexity: O(1) - Done entirely in place, without additional memory.
| Approach | Complexity |
|---|---|
| Transpose and Reverse | Time Complexity: O(n^2) - Because we loop through each element once. |
| Layer by Layer Rotation | Time Complexity: O(n^2) - Each individual element is moved once. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Transpose and Reverse | O(n^2) | O(1) | Best general approach; simple implementation and commonly expected in interviews |
| Layer by Layer Rotation | O(n^2) | O(1) | Useful when demonstrating in-place coordinate rotation and understanding matrix layers |
Rotate Image - Matrix - Leetcode 48 • NeetCode • 312,887 views views
Watch 9 more video solutions →Practice Rotate Image with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor