Rotate Image

Medium Arrays & Hashing In-place Transformations Original on LeetCode

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].length
  • 1 <= 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.

00:00
Testcase

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.

ApproachTimeSpace
Brute force (copy into a new matrix)O(n²)O(n²)
Four-way cycle per layerO(n²)O(1)
Optimal (transpose, then reverse each row)O(n²)O(1)

1Brute force (copy into a new matrix)

TimeO(n²)Each cell is written twice.
SpaceO(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.

  1. copy = new n x n matrix.
  2. For every (i, j): copy[j][n - 1 - i] = matrix[i][j].
  3. 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];
    }
}

2Four-way cycle per layer

TimeO(n²)Each cell is moved exactly once.
SpaceO(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.

  1. For layer from 0 to n / 2 - 1, let last = n - 1 - layer.
  2. For i from layer to last - 1, with off = i - layer: save top = matrix[layer][i].
  3. 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;
            }
        }
    }
}

3Optimal (transpose, then reverse each row)

TimeO(n²)Each pass touches every cell at most once.
SpaceO(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.

  1. For i < j: swap matrix[i][j] and matrix[j][i].
  2. 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;
            }
        }
    }
}

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.