LeetCode 48 · Medium · Math & Geometry

Rotate Image

Turn an n × n matrix 90 degrees clockwise. Do it in place: rearrange the values inside matrix itself, with no second matrix.

O(n²)time
O(1)space
4-way swaplayer by layer

rows separated by ; and values by commas · square, 1×1 to 6×6 · integers −99 to 999

public void rotate(int[][] matrix) { int l = 0; int r = matrix.length - 1; while (l < r) { for (int i = 0; i < r - l; i++) { int top = l; int bottom = r; int topLeft = matrix[top][l + i]; matrix[top][l + i] = matrix[bottom - i][l]; matrix[bottom - i][l] = matrix[bottom][r - i]; matrix[bottom][r - i] = matrix[top + i][r]; matrix[top + i][r] = topLeft; } r--; l++; }}
l, r
—
i
—
topLeft
—
cells moved
0

Why it works

  1. The easy way copies: out[c][n − 1 − r] = matrix[r][c] into a fresh matrix is O(n²) time but O(n²) extra space, which the problem forbids.
  2. Rotation moves values in 4-cycles: a cell on the top edge goes to the right edge, which goes to the bottom, then the left, then back to the top. Save one value in topLeft and the other three can shift into the freed cells in turn, going counter-clockwise.
  3. Layer by layer: the outer ring has r − l cycles; then l and r step in and the next ring rotates on its own. Every cell moves once: O(n²) time, one saved value: O(1) space.
  4. Pitfall: the offsets. With offset i, the four cells are [top][l+i], [bottom−i][l], [bottom][r−i] and [top+i][r]. Mixing up which side adds and which subtracts i rotates the corners correctly and scrambles everything else.
  5. Another in-place trick: transpose (swap matrix[r][c] with matrix[c][r]), then reverse each row. Two passes, same O(1) space.