Rotate Image

Medium#48rotate

You get a square n × n matrix, a picture. Turn it 90° clockwise in place: change the matrix itself, without a second one. Our example: the letters ABCD EFGH IJKL MNOP, row by row. After the turn it reads MIEA NJFB OKGC PLHD: the left column, read from the bottom up, has become the top row.

48 Rotate ImageWalkthrough · 1×

Example: the letters A to P, 4 × 4: two rings, three cycles of four on the outer one and one on the inner. Each step colours the cell a letter is read from and the cell it is written to.

01230123ABCDEFGHIJKLMNOPtmp
not moved yetin this cycle of fourread fromjust writtenin its final place

n = 4. Turning clockwise sends the cell (r, c) to (c, 3 - r): the top row becomes the right column

01/30
restart · back · play · step
Speed
1function rotate(m):
2 n = len(m)
3 for layer from 0 to n / 2 - 1:
4 last = n - 1 - layer
5 for i from layer to last - 1:
6 tmp = m[layer][i] // top
7 m[layer][i] = m[n - 1 - i][layer]
8 m[n - 1 - i][layer] = m[last][n - 1 - i]
9 m[last][n - 1 - i] = m[i][last]
10 m[i][last] = tmp
11 return m
state
n
4
layer
–
last
–
i
–
tmp
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A quarter turn sends the cell (r, c) to (c, n - 1 - r). Applied four times it comes back, so the cells split into cycles of four: one on each side of the same ring, the same distance from a corner.
  2. In a cycle each cell takes the value of the one behind it, so only the first value written over has to be kept aside: tmp holds the top cell until the right cell takes it.
  3. i runs from layer to last - 1, not to last: the corner at the end of a side is the start of the next side, and it already moved in the first cycle. One more step would turn it back.

Complexity

Time O(n²): every cell is moved once. Memory O(1): one spare variable, tmp, no second matrix.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.