#48

Medium

LeetCode Problem Workspace

Rotate Image

Rotate an n x n matrix 90 degrees clockwise in-place using array manipulation and mathematical indexing techniques efficiently.

array math matrix

Problem Statement

You are given an n x n 2D matrix representing an image, and your task is to rotate the image 90 degrees clockwise. You must perform this rotation in-place without allocating another 2D matrix, modifying the original matrix directly.

For example, given matrix = [[1,2,3],[4,5,6],[7,8,9]], after rotation the matrix becomes [[7,4,1],[8,5,2],[9,6,3]]. Constraints: n == matrix.length == matrix[i].length, 1 <= n <= 20, -1000 <= matrix[i][j] <= 1000.

Examples

Example 1

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

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

Example details omitted.

Example 2

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]]

Example details omitted.

Constraints

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

Solution Approach

Transpose the Matrix

Swap elements across the diagonal: for each element at (i,j) where i < j, swap with element at (j,i). This aligns rows with columns using the array plus math pattern.

Reverse Each Row

After transposition, reverse every row in the matrix. This shifts elements into correct 90-degree rotated positions, completing the clockwise rotation in-place without extra memory.

Iterative Layered Rotation (Alternative)

Rotate the matrix layer by layer from outermost to innermost, moving four elements at a time. This method uses direct index calculations, highlighting the array plus math pattern and avoiding full transposition.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) because each element is visited during transposition and row reversal. Space complexity is O(1) since rotation is done in-place without extra matrix allocation.

What Interviewers Usually Probe

Focus on in-place array manipulation rather than creating a new matrix.
Check if candidate uses both transpose and row reversal, showing understanding of index math.
Ask for an explanation of how indices map before and after rotation to test array plus math reasoning.

Common Pitfalls or Variants

Common pitfalls

Trying to rotate using an extra matrix, which violates in-place constraint.
Reversing columns instead of rows after transposition, leading to counter-clockwise rotation.
Incorrectly swapping elements during transposition, causing overwrites and wrong output.

Follow-up variants

Rotate matrix 180 degrees clockwise in-place.
Rotate non-square matrix with minimal extra space using similar index math.
Rotate matrix counter-clockwise using transpose and column reversal pattern.

FAQ

What is the most efficient method to solve Rotate Image?

Transpose the matrix and then reverse each row. This uses O(1) space and O(n^2) time for in-place rotation.

Can I use extra space to rotate the matrix?

No, the problem requires in-place rotation, so allocating another matrix violates constraints.

How do array plus math concepts apply to Rotate Image?

They guide how to calculate new positions for each element using index transformations without extra storage.

What if the matrix is not square?

Standard Rotate Image assumes n x n matrices; non-square matrices require adjusted index mapping or different rotation logic.

How do I avoid common pitfalls in Rotate Image?

Always swap elements correctly during transposition and reverse rows properly; double-check index calculations to prevent overwrites.

terminal

Solution

Solution 1: In-place Rotation

According to the problem requirements, we need to rotate $\text{matrix}[i][j]$ to $\text{matrix}[j][n - i - 1]$.

1

2

3

4

5

6

7

8

9

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n >> 1):
            for j in range(n):
                matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Continue Practicing

#782 transform to chessboard #840 magic squares in grid #883 projection area of 3d shapes