The problem
Rotate an n × n grid 90° clockwise, in place (without making a second grid).
Input: the 4 × 4 photo with tiles 1–16 Output: [[13,9,5,1],[14,10,6,2],[15,11,7,3],[16,12,8,4]]
Picture it
Picture a square photo made of tiles. A quarter turn is the same as two simple moves: first flip it over the diagonal from top-left to bottom-right (swap tile (r, c) with tile (c, r)), then mirror each row left-to-right.
How to recognise it
- You must transform a square grid and the problem insists on doing it in place (no second grid).
- The change is a geometric one: rotate, flip or mirror.
- Every cell moves to exactly one new cell, so no information is lost.
- Sizes are small (n up to 20), so the point is not speed but doing it with O(1) extra space.
- Rotations can be built from two simpler moves that are easy to do in place.
Start with brute force
Create a second grid and copy each cell to where it belongs. A cell at row r, column c moves to row c, column n − 1 − r after a quarter turn clockwise.
def rotate_brute(m):
n = len(m)
out = [[0] * n for _ in range(n)]
for r in range(n):
for c in range(n):
out[c][n - 1 - r] = m[r][c]
return out
Time is O(n²), which is already optimal because every cell must be touched. The problem is space: O(n²) for the second grid, and this version returns a new grid instead of changing the one it was given, so it breaks the "in place" rule. With n = 20 it is perfectly fast; the constraint is about the technique, not the size.
From brute force to the idea
- Look at where cells go. The first row of the old grid becomes the last column of the new one, the second row becomes the second-last column, and so on.
- Split the move in two. A quarter turn clockwise equals a transpose (swap
m[i][j]withm[j][i], a flip over the main diagonal) followed by reversing each row. - Transpose in place. Swapping pairs needs no extra grid. Only the cells above the diagonal (
j > i) are swapped, because each swap fixes two cells. - Reverse each row with
row.reverse(), which also works in place. - No return value. The function changes
mand returnsNone.
This is the key idea: replace one hard in-place move with two easy ones that each swap pairs of cells.
The key idea
Transpose, then reverse each row. O(n²), O(1) extra space.
Python solution
def rotate(m):
n = len(m)
for i in range(n):
for j in range(i + 1, n):
m[i][j], m[j][i] = m[j][i], m[i][j] # flip over the diagonal
for row in m:
row.reverse() # then mirror left-rightIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (copy to a second grid) | O(n²): every cell is copied once | O(n²): the second grid |
| Transpose and reverse (shown code) | O(n²): about n²/2 swaps, then n row reversals of n/2 swaps each | O(1): only loop variables |
Edge cases
- 1 × 1 grid: both loops do nothing useful and the grid is unchanged.
- 2 × 2 grid (
[[1, 2], [3, 4]]): becomes[[3, 1], [4, 2]]. - Four rotations: four calls restore the original grid.
- Empty grid (
[]): the loops do not run and nothing breaks. - Odd sizes: the middle cell stays where it is, and the transpose touches only cells off the diagonal, so nothing special is needed.
- Non-square grids: the code assumes a square grid, as the problem promises. A rotation changes the shape of a rectangle, so a 3 × 2 grid raises an
IndexErrorand a 2 × 3 grid comes out scrambled.
Common mistakes
- Swapping over the full range (
for j in range(n)), which swaps every pair twice and undoes the transpose. The grid is only mirrored left to right. - Skipping the row reversal, which gives a flip over the diagonal, not a rotation.
- Reversing the order of rows instead of each row, which turns the grid counter-clockwise instead.
- Building the second grid with
[[0] * n] * n, which makes every row the same list.
Rotate the grid 90° counter-clockwise in place. For [[1, 2, 3], [4, 5, 6], [7, 8, 9]] the result is [[3, 6, 9], [2, 5, 8], [1, 4, 7]]. Describe your approach, then write it if you like.
Compare with our answer
Keep the transpose, but instead of reversing each row, reverse the order of the rows.
def rotate_counter(m):
n = len(m)
for i in range(n):
for j in range(i + 1, n):
m[i][j], m[j][i] = m[j][i], m[i][j] # transpose
m.reverse() # flip top to bottom
For the example it gives [[3, 6, 9], [2, 5, 8], [1, 4, 7]]. Time O(n²), space O(1). Doing it for a clockwise turn three times gives the same result.
A strong answer mentions: transpose first, reversing the row order (not each row), and that m.reverse() is in place too.
1. You must flip a square grid so that the left column becomes the top row, in place. Which approach fits best?
Transposing swaps cell pairs in place, and one more reversal chooses the direction. Copying uses O(n²) extra space, and a vertical mirror alone cannot turn rows into columns.
2. Why does the transpose loop use range(i + 1, n) for the inner loop?
Swapping m[i][j] with m[j][i] moves two cells at once, so visiting only one of each pair is enough. Visiting both would swap each pair twice. A swap with itself is harmless.
3. A learner changes the inner loop to for j in range(n). What does rotate do to [[1, 2, 3], [4, 5, 6], [7, 8, 9]]?
Every pair is swapped twice, which undoes the transpose, and then each row is reversed. The result is only a left-right mirror. The other three results come from different changes (no reversal, reversing the rows instead, or the correct code).
Score 60% or more and the lesson is marked complete.