title: Rotate Image
slug: rotate-image
difficulty: medium
leetcode_id: 48
leetcode_url: https://leetcode.com/problems/rotate-image/
categories:
  - arrays
  - math
patterns:
  - slug: matrix-manipulation
    is_optimal: true

function_signature: "def rotate(matrix: list[list[int]]) -> None:"

test_cases:
  visible:
    - input: { matrix: [[1, 2, 3], [4, 5, 6], [7, 8, 9]] }
      expected: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
    - input: { matrix: [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]] }
      expected: [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]
  hidden:
    - input: { matrix: [[1]] }
      expected: [[1]]
    - input: { matrix: [[1, 2], [3, 4]] }
      expected: [[3, 1], [4, 2]]
    - input: { matrix: [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]] }
      expected: [[13, 9, 5, 1], [14, 10, 6, 2], [15, 11, 7, 3], [16, 12, 8, 4]]

description: |
  You are given an `n × n` 2D matrix representing an image. Rotate the image by **90 degrees** (clockwise).

  You have to rotate the image **in-place**, which means you have to modify the input 2D matrix directly. **DO NOT** allocate another 2D matrix and do the rotation.

constraints: |
  - `n == matrix.length == matrix[i].length`
  - `1 <= n <= 20`
  - `-1000 <= matrix[i][j] <= 1000`

examples:
  - input: "matrix = [[1,2,3],[4,5,6],[7,8,9]]"
    output: "[[7,4,1],[8,5,2],[9,6,3]]"
    explanation: "The 3×3 matrix is rotated 90 degrees clockwise."
  - input: "matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]"
    output: "[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]"
    explanation: "The 4×4 matrix is rotated 90 degrees clockwise."

explanation:
  intuition: |
    Rotating a matrix 90° clockwise might seem like it requires complex index manipulation, but there's a beautiful mathematical insight: the rotation can be decomposed into **two simple operations**.

    Think of it like this: a 90° clockwise rotation moves element at position `(i, j)` to position `(j, n-1-i)`. This transformation happens to be equivalent to:
    1. **Transpose** the matrix (swap rows and columns)
    2. **Reverse** each row

    Visually for a 3×3 matrix:
    ```
    Original    Transpose    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
    ```

    Both operations can be done in-place with simple swaps, making this the cleanest approach.

  approach: |
    We solve this using **Transpose + Reverse**:

    **Step 1: Transpose the matrix**

    - Swap `matrix[i][j]` with `matrix[j][i]` for all `i < j`
    - Only iterate over the upper triangle (`j > i`) to avoid undoing swaps
    - After this, rows become columns and vice versa

    &nbsp;

    **Step 2: Reverse each row**

    - For each row, reverse the order of elements
    - Python's `row.reverse()` does this in-place

    &nbsp;

    **Why does this work?**

    - Transpose: `(i, j) → (j, i)`
    - Reverse row: `(j, i) → (j, n-1-i)`
    - Combined: `(i, j) → (j, n-1-i)` — exactly 90° clockwise rotation!

    &nbsp;

    This decomposition turns a complex problem into two simple, understandable operations.

  common_pitfalls:
    - title: Transposing the Entire Matrix Twice
      description: |
        When transposing, only swap elements in the **upper triangle** (where `j > i`). If you iterate over all pairs, you'll swap `(i,j)` and then `(j,i)` — undoing the first swap!

        The inner loop should start at `j = i + 1`, not `j = 0`.
      wrong_approach: "for j in range(n): swap (i,j) and (j,i)"
      correct_approach: "for j in range(i + 1, n): swap (i,j) and (j,i)"

    - title: Confusing Clockwise and Counterclockwise
      description: |
        - **Clockwise 90°**: Transpose, then reverse each row
        - **Counterclockwise 90°**: Transpose, then reverse each column (or reverse rows first, then transpose)

        Getting this wrong rotates in the opposite direction.
      wrong_approach: "Reversing columns for clockwise rotation"
      correct_approach: "Transpose + reverse rows = clockwise"

    - title: Allocating Extra Space
      description: |
        The problem explicitly requires in-place rotation. Both transpose and row reversal can be done with swaps using O(1) extra space.

        Creating a new matrix and copying values violates the constraint.
      wrong_approach: "Creating a new n×n matrix for the result"
      correct_approach: "Use in-place swaps only"

  key_takeaways:
    - "**Decompose complex transformations**: 90° rotation = transpose + reverse"
    - "**Upper triangle only for transpose**: Avoid undoing swaps by only iterating where `j > i`"
    - "**Know your rotations**: Clockwise vs counterclockwise requires different orderings"
    - "**In-place operations are possible**: Most matrix transformations can be done with careful swapping"

  time_complexity: "O(n²). We visit each element a constant number of times during transpose and reversal."
  space_complexity: "O(1). All operations are done in-place using only swaps."

solutions:
  - approach_name: Transpose + Reverse
    is_optimal: true
    code: |
      def rotate(matrix: list[list[int]]) -> None:
          n = len(matrix)

          # Step 1: Transpose (swap across main diagonal)
          # Only iterate upper triangle to avoid undoing swaps
          for i in range(n):
              for j in range(i + 1, n):
                  matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

          # Step 2: Reverse each row
          for row in matrix:
              row.reverse()
    explanation: |
      **Time Complexity:** O(n²) — Visit each element constant times.

      **Space Complexity:** O(1) — In-place swaps only.

      Transpose swaps elements across the main diagonal, converting rows to columns. Reversing each row then completes the 90° clockwise rotation. Both operations are simple and in-place.

  - approach_name: Layer-by-Layer Rotation
    is_optimal: false
    code: |
      def rotate(matrix: list[list[int]]) -> None:
          n = len(matrix)

          # Rotate layer by layer from outside to inside
          for layer in range(n // 2):
              first, last = layer, n - 1 - layer

              for i in range(first, last):
                  offset = i - first

                  # Save top element
                  top = matrix[first][i]

                  # Move left → top
                  matrix[first][i] = matrix[last - offset][first]

                  # Move bottom → left
                  matrix[last - offset][first] = matrix[last][last - offset]

                  # Move right → bottom
                  matrix[last][last - offset] = matrix[i][last]

                  # Move top → right (using saved value)
                  matrix[i][last] = top
    explanation: |
      **Time Complexity:** O(n²) — Visit each element once.

      **Space Complexity:** O(1) — Only one temp variable.

      Rotate the matrix layer by layer, from the outermost ring inward. For each position in a layer, perform a four-way swap moving elements clockwise. Correct but more complex to implement and understand than transpose+reverse.
