Rotate Image
Last Updated: March 22, 2026
Understanding the Problem
Matrix rotation is one of those problems that looks intimidating at first glance, but once you see the right decomposition, it becomes surprisingly clean. The key challenge here is doing it in-place, without allocating a new matrix.
We need to rotate an n x n matrix 90 degrees clockwise, and we must do it in-place. So what does a 90-degree clockwise rotation actually do to each element?
If you look at where element (i, j) ends up after rotation, you'll notice a pattern. The first row [1, 2, 3] becomes the last column [1, 2, 3] (reading top-to-bottom). The last row [7, 8, 9] becomes the first column [7, 8, 9] (reading top-to-bottom). More precisely, element at position (i, j) moves to position (j, n - 1 - i).
Key Constraints:
1 <= n <= 20means with n at most 20, the matrix has at most 400 elements. Even O(n^4) would be fast enough, so time complexity isn't a concern. The focus is on space: can we avoid allocating a second matrix?n == matrix.length == matrix[i].lengthmeans the matrix is always square. This is important because rotation of a rectangular matrix would change its dimensions, but a square matrix stays the same size.-1000 <= matrix[i][j] <= 1000means values fit in any integer type. No overflow concerns.
Approach 1: Using Extra Space
Intuition
The most straightforward approach is to figure out where each element goes and copy it there. If we trace what happens during a 90-degree clockwise rotation, element at (i, j) moves to (j, n - 1 - i).
So we can create a new matrix, place every element in its rotated position, then copy everything back to the original matrix. This doesn't satisfy the "no extra matrix" constraint, but it's a great starting point for understanding the index mapping.
Algorithm
- Create a new n x n matrix
rotated. - For each element at position
(i, j)in the original matrix, place it at(j, n - 1 - i)inrotated. - Copy all values from
rotatedback into the original matrix.
Code
- Time Complexity: O(n^2). We iterate through all n^2 elements twice: once to build the rotated matrix, once to copy back.
- Space Complexity: O(n^2). We allocate a completely new n x n matrix.
This approach works correctly but allocates an entire n x n matrix just to hold intermediate results. The problem explicitly asks us not to do this. Every element gets written twice: once into the new matrix, then copied back. Can we decompose the rotation into simpler operations that each work in-place?
Approach 2: Transpose + Reverse
Intuition
Here's a neat observation: a 90-degree clockwise rotation is the same as transposing the matrix and then reversing each row. Let's see why.
Transposing swaps rows and columns: element (i, j) moves to (j, i). After that, reversing each row sends element (j, i) to (j, n - 1 - i). Put them together, and (i, j) -> (j, n - 1 - i), which is exactly the 90-degree clockwise rotation formula we derived earlier.
Both transposing and reversing can be done in-place with simple swaps. No extra matrix needed.
The rotation formula is (i, j) -> (j, n - 1 - i). We can decompose this into two steps:
- Transpose:
(i, j) -> (j, i)swaps the row and column indices. - Reverse row:
(j, i) -> (j, n - 1 - i)mirrors each row horizontally.
Composing these gives us the full rotation. This decomposition also makes it easy to derive rotations in other directions. For 90-degree counter-clockwise, you'd transpose then reverse each column (or equivalently, reverse each row then transpose).
Algorithm
- Transpose the matrix: For each pair
(i, j)wherei < j, swapmatrix[i][j]withmatrix[j][i]. - Reverse each row: For each row, swap elements from the outside in (left and right pointers moving toward the center).
Code
- Time Complexity: O(n^2). Transposing touches n(n-1)/2 pairs, and reversing n rows of n elements each takes n^2/2 swaps. Both are O(n^2).
- Space Complexity: O(1). We only use a single temporary variable for swapping. Everything is done in-place.
This approach touches every element twice, once during transpose, once during row reversal. Can we move each element directly to its final position, rotating four elements at a time in a cycle?
Approach 3: Four-Way Swap (Layer by Layer)
Intuition
Instead of decomposing the rotation into transpose + reverse, we can rotate elements directly. The key observation is that every element is part of a cycle of four: rotating the matrix moves element A to B's position, B to C's, C to D's, and D back to A's.
Think of the matrix as concentric square layers, like the rings of an onion. The outermost layer is the border elements, the next layer is one step inward, and so on. For each layer, we walk along the top edge and perform a four-way swap for each position.
For a position (top, left + i) on the top edge of a layer:
- Top moves to Right:
(top, left + i)to(top + i, right) - Right moves to Bottom:
(top + i, right)to(bottom, right - i) - Bottom moves to Left:
(bottom, right - i)to(bottom - i, left) - Left moves to Top:
(bottom - i, left)to(top, left + i)
By saving one value in a temp variable and rotating the other three, we place all four elements in their correct positions in one shot.
This approach is often what interviewers are looking for because it demonstrates you can reason about index transformations directly. If you get confused by the indices during the interview, draw a 4x4 grid and trace one specific position through the four-way swap. For example, trace where (0, 1) goes: (0,1) -> (1,3) -> (3,2) -> (2,0) -> (0,1). Seeing concrete numbers makes the pattern click.
Algorithm
- Process the matrix layer by layer, from the outermost layer inward. Each layer is defined by its
top,bottom,left, andrightboundaries. - For each layer, iterate through positions along the top edge (excluding the last element, since it belongs to the next side).
- At each position, perform a four-way swap:
- Save the top element.
- Move the left element to the top.
- Move the bottom element to the left.
- Move the right element to the bottom.
- Place the saved top element at the right.
- After processing all positions in the layer, shrink the boundaries inward and repeat.
Code
- Time Complexity: O(n^2). Each of the n^2 elements is moved exactly once. The nested loops (layers x positions per layer) cover all n^2 elements.
- Space Complexity: O(1). We only use one temporary variable regardless of the matrix size.