Rotate Image
Rotate Image is a medium arrays & hashing problem solved with the in-place transformations pattern.
The best approach, optimal (transpose, then reverse each row), runs in O(n²) time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (copy into a new matrix) up.
Problem
You are given a square n x n grid of integers, matrix, that represents an image. Turn the image 90 degrees clockwise.
Do it in place: change the cells of matrix itself rather than building and returning another grid. After the call, matrix must hold the rotated image.
Examples
Example 1
- Input
matrix = [[4,8,1],[6,2,9],[3,7,5]]- Output
[[3,6,4],[7,2,8],[5,9,1]]- Why
- The left column read from bottom to top (3, 6, 4) becomes the new top row, and so on.
Example 2
- Input
matrix = [[10,-1],[0,5]]- Output
[[0,10],[5,-1]]- Why
- Each corner moves one step clockwise: 10 goes top-right, -1 bottom-right, 5 bottom-left, 0 top-left.
Example 3
- Input
matrix = [[42]]- Output
[[42]]- Why
- A single cell does not move.
Constraints
n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000- Rotate in place: do not allocate a second matrix in the final solution.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (copy into a new matrix) | O(n²) | O(n²) |
| Four-way cycle per layer | O(n²) | O(1) |
| Optimal (transpose, then reverse each row) | O(n²) | O(1) |
1Brute force (copy into a new matrix)
O(n²)Each cell is written twice.O(n²)A second full matrix, which the in-place rule forbids in the final answer.Build a fresh n x n matrix where the value at (i, j) of the original is written to (j, n - 1 - i). Then copy everything back into the input.
- copy = new n x n matrix.
- For every (i, j): copy[j][n - 1 - i] = matrix[i][j].
- Copy all cells of copy back into matrix.
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int[][] copy = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
copy[j][n - 1 - i] = matrix[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
matrix[i][j] = copy[i][j];
}
}class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
copy = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
copy[j][n - 1 - i] = matrix[i][j]
for i in range(n):
for j in range(n):
matrix[i][j] = copy[i][j]class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
vector<vector<int>> copy(n, vector<int>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
copy[j][n - 1 - i] = matrix[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
matrix[i][j] = copy[i][j];
}
};function rotate(matrix) {
const n = matrix.length;
const copy = Array.from({ length: n }, () => new Array(n).fill(0));
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
copy[j][n - 1 - i] = matrix[i][j];
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
matrix[i][j] = copy[i][j];
}2Four-way cycle per layer
O(n²)Each cell is moved exactly once.O(1)Only one temporary value.Peel the matrix into square rings. In each ring, every cell on the top edge belongs to a cycle of four cells (top, right, bottom, left). Rotate each cycle with one temporary variable.
- For layer from 0 to n / 2 - 1, let last = n - 1 - layer.
- For i from layer to last - 1, with off = i - layer: save top = matrix[layer][i].
- left -> top, bottom -> left, right -> bottom, saved top -> right.
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int layer = 0; layer < n / 2; layer++) {
int last = n - 1 - layer;
for (int i = layer; i < last; i++) {
int off = i - layer;
int top = matrix[layer][i];
matrix[layer][i] = matrix[last - off][layer];
matrix[last - off][layer] = matrix[last][last - off];
matrix[last][last - off] = matrix[i][last];
matrix[i][last] = top;
}
}
}
}class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
for layer in range(n // 2):
last = n - 1 - layer
for i in range(layer, last):
off = i - layer
top = matrix[layer][i]
matrix[layer][i] = matrix[last - off][layer]
matrix[last - off][layer] = matrix[last][last - off]
matrix[last][last - off] = matrix[i][last]
matrix[i][last] = topclass Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int layer = 0; layer < n / 2; layer++) {
int last = n - 1 - layer;
for (int i = layer; i < last; i++) {
int off = i - layer;
int top = matrix[layer][i];
matrix[layer][i] = matrix[last - off][layer];
matrix[last - off][layer] = matrix[last][last - off];
matrix[last][last - off] = matrix[i][last];
matrix[i][last] = top;
}
}
}
};function rotate(matrix) {
const n = matrix.length;
for (let layer = 0; layer < Math.floor(n / 2); layer++) {
const last = n - 1 - layer;
for (let i = layer; i < last; i++) {
const off = i - layer;
const top = matrix[layer][i];
matrix[layer][i] = matrix[last - off][layer];
matrix[last - off][layer] = matrix[last][last - off];
matrix[last][last - off] = matrix[i][last];
matrix[i][last] = top;
}
}
}3Optimal (transpose, then reverse each row)
O(n²)Each pass touches every cell at most once.O(1)Swaps use one temporary value.A clockwise quarter turn equals a transpose (cell (i, j) swaps with (j, i)) followed by a left-right mirror of every row. After the transpose, (i, j) holds the old (j, i); reversing the row moves it to column n - 1 - j, which is exactly where the rotation sends it. Both steps are simple swaps in place.
- For i < j: swap matrix[i][j] and matrix[j][i].
- For every row: two pointers from both ends, swapping toward the middle.
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int t = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = t;
}
for (int[] row : matrix) {
int l = 0, r = n - 1;
while (l < r) {
int t = row[l];
row[l++] = row[r];
row[r--] = t;
}
}
}
}class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
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:
l, r = 0, n - 1
while l < r:
row[l], row[r] = row[r], row[l]
l += 1
r -= 1class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
swap(matrix[i][j], matrix[j][i]);
for (auto& row : matrix) {
int l = 0, r = n - 1;
while (l < r) swap(row[l++], row[r--]);
}
}
};function rotate(matrix) {
const n = matrix.length;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++) {
const t = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = t;
}
for (const row of matrix) {
let l = 0, r = n - 1;
while (l < r) {
const t = row[l];
row[l++] = row[r];
row[r--] = t;
}
}
}Edge cases to test
- n = 1 (nothing changes)
- n = 2 (one cycle of four cells)
- Odd n, where the centre cell stays put
- Repeated and negative values
Hints
Hint 1
Write down where cell (i, j) ends up after a clockwise quarter turn. The answer is (j, n - 1 - i).
Hint 2
A quarter turn can be built from two simple reflections that are each easy to do in place.
Hint 3
Transpose the matrix (swap across the main diagonal), then reverse every row.
FAQ
What is the best time complexity for Rotate Image?
Optimal (transpose, then reverse each row) runs in O(n²) time and O(1) extra space. Each pass touches every cell at most once.
Which pattern does Rotate Image use?
It is a arrays & hashing problem that uses the in-place transformations pattern. Other problems with the same pattern: Set Matrix Zeroes, Find All Duplicates in an Array, First Missing Positive.
Is there a brute force solution for Rotate Image?
Yes. Brute force (copy into a new matrix) takes O(n²) time and O(n²) space. Build a fresh n x n matrix where the value at (i, j) of the original is written to (j, n - 1 - i).
Which edge cases should I test for Rotate Image?
n = 1 (nothing changes); n = 2 (one cycle of four cells); Odd n, where the centre cell stays put; Repeated and negative values.