Skip to main content

48 - Rotate Image

Difficulty: Medium | Pattern: Matrix Manipulation | Company tags: Amazon, Apple, Facebook, Microsoft

Problem Statement​

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees clockwise.

You must do this in-place — do not allocate another 2D matrix.

Example:

Input:                Output:
[[1,2,3],            [[7,4,1],
 [4,5,6],             [8,5,2],
 [7,8,9]]             [9,6,3]]

Approach: Transpose + Reverse Rows — O(n²), O(1)​

Key insight: A 90° clockwise rotation equals:

  1. Transpose the matrix (flip along main diagonal: matrix[i][j] ↔ matrix[j][i])
  2. Reverse each row
def rotate(matrix: list[list[int]]) -> None:
    n = len(matrix)
    
    # Step 1: Transpose
    for i in range(n):
        for j in range(i+1, n):  # only upper triangle to avoid double-swapping
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    
    # Step 2: Reverse each row
    for row in matrix:
        row.reverse()

Algorithm Flow​

Why This Works​

For a 90° clockwise rotation, cell (i, j) goes to (j, n-1-i).

  • After transpose: (i, j) → (j, i)
  • After reverse row: (j, i) → (j, n-1-i) ✓

Dry Run​

Original:    After Transpose:    After Reverse Rows:
1 2 3        1 4 7               7 4 1
4 5 6   →    2 5 8       →       8 5 2
7 8 9        3 6 9               9 6 3

Transpose swaps: (0,1)↔(1,0): 2↔4, (0,2)↔(2,0): 3↔7, (1,2)↔(2,1): 6↔8

Other Rotation Directions​

RotationSteps
90° clockwiseTranspose + reverse each row
90° counter-clockwiseReverse each row + transpose
180°Reverse each row + reverse matrix (or transpose twice)

Edge Cases​

  • 1×1 matrix → already "rotated", no change needed
  • 2×2 matrix → 1 swap in transpose, 1 reverse per row
  • Already rotated matrix → applying again returns next 90° position

Complexity​

  • Time: O(n²) — every cell is visited a constant number of times
  • Space: O(1) — in-place, no extra matrix

Key pattern to remember: transpose then reverse = 90° clockwise. For counter-clockwise, reverse first then transpose.

Key Terms​

TermDefinition
TransposeReflecting a matrix across its main diagonal, swapping matrix[i][j] with matrix[j][i].
In-placeModifying the input structure directly instead of allocating a second matrix, keeping space at O(1).
Layer/ring rotationAlternative approach that rotates the matrix one concentric square ring at a time via 4-way element swaps.
Row reversalReversing the order of elements within each row, used here after transposing to complete the clockwise rotation.

FAQ​

  1. Can this be solved without extra space? Yes — that's the point of transpose + reverse; both operations mutate the input matrix directly, giving O(1) auxiliary space.
  2. What if the matrix is empty or 1×1? An empty matrix needs no work, and a 1×1 matrix is unchanged since transposing and reversing a single element are no-ops.
  3. How would you rotate counter-clockwise instead? Reverse each row first, then transpose — the mirror image of the clockwise steps.
  4. Why only iterate j from i+1 in the transpose loop? Iterating the full range would swap every pair twice, undoing the transpose; restricting to the upper triangle (j > i) ensures each pair swaps exactly once.
  5. What if the matrix isn't square (n x m)? The in-place transpose-and-reverse trick only works for square matrices; a non-square rotation must build a new m x n output matrix since dimensions change.

Quick Revision​

  • Problem: rotate an n×n matrix 90° clockwise in place, no extra matrix allowed.
  • Core trick: 90° clockwise = transpose + reverse each row.
  • Transpose: swap matrix[i][j] and matrix[j][i] for j > i only (avoids double-swapping).
  • Reverse: flip each row left-to-right after transposing.
  • Cell (i, j) maps to (j, n-1-i) under a true 90° clockwise rotation — verify transpose+reverse reproduces this.
  • Counter-clockwise is the reverse order: reverse rows first, then transpose.
  • 180° rotation: reverse rows and reverse the matrix (or transpose twice).
  • Time O(n²), space O(1) — every cell touched a constant number of times.