LeetCode 48 · Math & Geometry

Rotate Image, explained with a picture

Turning a photo a quarter turn, tile by tile.

MediumMath & Geometry
▶ Watch it step by step

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

  1. 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.
  2. Split the move in two. A quarter turn clockwise equals a transpose (swap m[i][j] with m[j][i], a flip over the main diagonal) followed by reversing each row.
  3. 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.
  4. Reverse each row with row.reverse(), which also works in place.
  5. No return value. The function changes m and returns None.

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-right

In 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

ApproachTimeSpace
Brute force (copy to a second grid)O(n²): every cell is copied onceO(n²): the second grid
Transpose and reverse (shown code)O(n²): about n²/2 swaps, then n row reversals of n/2 swaps eachO(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 IndexError and 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.
Your turn: counter-clockwise

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.

Check what stuck

1. You must flip a square grid so that the left column becomes the top row, in place. Which approach fits best?

2. Why does the transpose loop use range(i + 1, n) for the inner loop?

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]]?

Score 60% or more and the lesson is marked complete.