{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Rotate Image – Solution & Complexity

Interview solutions
/
Rotate Image

Solution Walkthrough

  1. Step 1: Understanding the Problem

    • You must rotate an n x n matrix 90 degrees clockwise.
    • A naive approach allocates a brand new matrix and copies each cell to its rotated position — simple to reason about, but uses O(n^2) extra space.
    • The interesting version of this problem does it in place with only O(1) extra space, which is what most interviewers are really asking for.

  2. Step 2: The In-Place Trick: Transpose, Then Reverse

    • Rotating 90 degrees clockwise can be decomposed into two simpler, well-known in-place operations:
      1. Transpose the matrix (swap matrix[i][j] with matrix[j][i] for all i < j) — this flips the matrix across its main diagonal.
      2. Reverse each row — this mirrors every row horizontally.
    • Doing both in sequence produces exactly the 90-degree clockwise rotation, using only the original array's memory.

  3. Step 3: Why Transpose + Reverse Works

    • After transposing, matrix[i][j] holds the original matrix[j][i]. The first column now reads top-to-bottom as the original first row read left-to-right.
    • Reversing each row then flips that column's order, which is exactly what a clockwise rotation does: the original first row becomes the new last column, read top-to-bottom.
    • Trace on [[1,2,3],[4,5,6],[7,8,9]]: transpose gives [[1,4,7],[2,5,8],[3,6,9]]; reversing each row gives [[7,4,1],[8,5,2],[9,6,3]] — the correct rotation.

  4. Step 4: Final Solution (all languages)

    Both the transpose and the row-reversal are O(n^2) (every cell is touched once), giving O(n^2) time and O(1) extra space overall — optimal, since you must write every one of the n^2 output cells.

    def rotate(matrix: list[list[int]]) -> list[list[int]]:
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()
    return matrix

  5. Step 5: Common mistakes & interviewer follow-ups

    • Transposing the full matrix (both i < j and i > j) undoes itself — only swap the upper triangle (j > i) once.
    • Reversing columns instead of rows, or transposing across the anti-diagonal instead of the main diagonal, produces a counter-clockwise rotation or a flip instead of the required clockwise rotation.
    • Follow-ups: how would you rotate 90 degrees counter-clockwise (reverse columns/rows in a different order)? How would you handle a non-square m x n matrix, where true in-place rotation isn't possible without extra bookkeeping?

FAQ

See also

Practice Rotate Image online (run code in the browser)Search a 2D Matrix solution (medium)Set Matrix Zeroes solution (medium)Spiral Matrix solution (medium)Spiral Matrix II solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?