Rotate Image
Understanding the Problem
We need to rotate an n x n matrix 90 degrees clockwise, and we must do it in-place. The first step is to figure out where each element moves.
Track where one row goes. The first row [1, 2, 3] becomes the last column, read top to bottom. The last row [7, 8, 9] becomes the first column. Generalizing this, the element at position (i, j) moves to position (j, n - 1 - i). The row index i becomes the new column index, and the old column index j becomes the new row index, counted from the bottom. This single formula is the foundation for every approach below.
Key Constraints:
n == matrix.length == matrix[i].lengthmeans the matrix is always square. Rotating a rectangular matrix would swap its dimensions, but a square matrix keeps the same shape, which is what makes an in-place rotation possible.1 <= n <= 20keeps the matrix small (at most 400 elements), so time is not the constraint. The real requirement is in the problem statement: rotate in-place, without allocating a second matrix.-1000 <= matrix[i][j] <= 1000means values fit in a 32-bit integer with no overflow concerns. Every approach only moves values around, never adds them, so the value range never matters beyond storage.
Approach 1: Using Extra Space
Intuition
Apply the rotation formula directly. Element (i, j) moves to (j, n - 1 - i), so we can allocate a second matrix, write every element into its rotated position, then copy the result back into the original.
This violates the in-place constraint, but it isolates the index mapping from the harder problem of doing the same moves without a scratch buffer. Once the formula is correct here, the later approaches reuse it.
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.
Visualization and Code
Loading animation...
- 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 allocates an entire n x n matrix to hold intermediate results, which the problem forbids, and it writes every element twice. The next approach decomposes the rotation into two passes that each rearrange the matrix in-place, removing the extra storage.
Approach 2: Transpose + Reverse
Intuition
A 90-degree clockwise rotation equals transposing the matrix and then reversing each row. The two operations compose into the rotation formula.
Transposing swaps rows and columns, sending element (i, j) to (j, i). Reversing each row then sends (j, i) to (j, n - 1 - i). Composing the two gives (i, j) -> (j, n - 1 - i), the rotation formula from the start of the chapter. Both transposing and reversing each row are in-place operations built from swaps, so no second matrix is required.
The same decomposition produces rotations in other directions, which is a useful check that the reasoning is about index transforms rather than a memorized recipe. For a 90-degree counter-clockwise rotation, reverse each row first and then transpose. For a 180-degree rotation, reverse every row and every column. Each direction is a different composition of transpose and reflect.
Algorithm
- Transpose the matrix: For each pair
(i, j)wherei < j, swapmatrix[i][j]withmatrix[j][i]. Thei < jbound visits each off-diagonal pair once; visiting every pair would swap each one twice and undo the transpose. - Reverse each row: For each row, swap elements from the outside in (left and right pointers moving toward the center).
Visualization and Code
Loading animation...
- 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 and once during row reversal. The next approach moves each element straight to its final position by rotating four elements at a time, so each element is written only once.
Approach 3: Four-Way Swap (Layer by Layer)
Intuition
Instead of decomposing the rotation into transpose plus reverse, move elements directly. Every element belongs to a cycle of four: the rotation sends element A to B's position, B to C's, C to D's, and D back to A's. The four positions in each cycle are the same distance from the center, one on each side of the matrix.
The matrix is a set of concentric square layers. The outermost layer is the border, the next layer is one ring inward, and so on. For each layer, walk along the top edge and perform one four-way swap per 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)
Saving one value in a temporary variable lets us move the other three without losing data, so all four elements reach their correct positions in a single pass over the layer.
To confirm the indices, draw a 4x4 grid and trace one position through the rotation formula (i, j) -> (j, n - 1 - i) with n = 4. Starting at (0, 1): it moves to (1, 3), then (3, 2), then (2, 0), then back to (0, 1). Those four cells are exactly one four-way swap. The code writes them in the reverse order of this cycle: it caches the top element, fills it from the left, the left from the bottom, the bottom from the right, and the right from the cached top. Pulling values backward along the cycle moves each one forward into its rotated slot.
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.
Visualization and Code
Loading animation...
- 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.