You are given an n x n matrix representing an image. Rotate it by 90 degrees clockwise, in place: you must change the given matrix directly and not allocate another matrix.
Example 1
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
The first column read from bottom to top
7,4,1 becomes the first row.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]]
Constraints
- 1 <= n <= 20
- -1000 <= matrix[i][j] <= 1000
Hints
Frequently asked at: Microsoft, Amazon, Apple, Adobe, Samsung
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Copying into a new matrix with new[j][n-1-i] = old[i][j] is easy but uses O(n^2) extra space, which is not allowed. A clockwise rotation can be split into two in-place steps: a transpose (flip over the main diagonal) followed by reversing every row (flip left to right). Each step is a series of simple swaps.
Algorithm
- For every
i < j, swapmatrix[i][j]andmatrix[j][i](transpose). - Reverse each row.
- The matrix is now rotated 90 degrees clockwise.
Time:
O(n^2)Space: O(1)Interview tip: When transposing, loop only over
j > i. Swapping over the full matrix swaps every pair twice and leaves it unchanged. Follow-up: for anticlockwise, reverse each row first and then transpose.class Solution: def rotate(self, matrix: List[List[int]]) -> None: n = len(matrix) # 1) transpose: swap across the main diagonal for i in range(n): for j in range(i + 1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # 2) reverse every row for row in matrix: row.reverse()Ctrl + Enter runs the examples