Rotate Image

The problem

You are given an n × n grid of numbers, matrix. The code calls n size. Turn it 90 degrees clockwise. Change matrix itself: do not build and return a second grid.

Example 1

Input: matrix = [[10, 11, 12, 13], [14, 15, 16, 17], [18, 19, 20, 21], [22, 23, 24, 25]]

Output: [[22, 18, 14, 10], [23, 19, 15, 11], [24, 20, 16, 12], [25, 21, 17, 13]]

The top row, 10 to 13, is now the right column, read top to bottom.

	c0	c1	c2	c3
r0	22	18	14	10
r1	23	19	15	11
r2	24	20	16	12
r3	25	21	17	13

Example 2

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

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

The left column, read bottom to top, becomes the top row: 4, 9, 3.

Example 3

Input: matrix = [[6]]

Output: [[6]]

A single cell looks the same after any turn.

Constraints

• 1 ≤ n ≤ 20
• −1,000 ≤ matrix[i][j] ≤ 1,000
• The grid is square: n rows and n columns.

Clarifying questions

Clockwise or counterclockwise?

Clockwise. The top row becomes the right column.

Must it be in place?

Yes. The grid itself must change, so the best answer uses no second grid.

Is the grid always square?

Yes, n × n. A turn of a non-square grid would change its shape.

Where does matrix[i][j] go?

To row j, column n − 1 − i.

Spot the pattern

Rotation looks like a hard move, but it breaks into two easy ones. A transpose flips the grid across its main diagonal, so rows become columns. Reversing each row then mirrors it left to right. Both are plain swaps of two cells, so they need no extra grid.

Solutions

Copy to a new gridO(n²), O(n²) spaceTranspose, then reverseO(n²), O(1) space

Show all

Rotating four cells at a time, ring by ring, also works in place with the same Big O. Transpose and reverse is easier to get right.

Copy to a new grid O(n²), O(n²) space

The idea

Make a new empty grid rotated. Each value matrix[i][j] belongs at rotated[j][size − 1 − i]: row 0 becomes the last column, row 1 the column before it, and so on. Then copy rotated back into matrix.

It is easy to get right. But the problem asks for an in-place change, and rotated is a whole second grid.

Walkthrough

matrix row 0

100111122133

	c0	c1	c2	c3
r0	·	·	·	·
r1	·	·	·	·
r2	·	·	·	·
r3	·	·	·	·

1. rotated = [[0] * size for _ in range(size)]
2. for i in range(size):
3. for j in range(size):
4. rotated[j][size - 1 - i] = matrix[i][j]
5. matrix[:] = rotated # copy the rows back

Make a new empty grid, rotated. Each value in matrix row i goes to column size − 1 − i of rotated.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Copy to a new grid: value [i][j] lands at [j][size - 1 - i]. Then copy back.
    // O(n^2) time, and the second grid costs O(n^2) memory.
    public void rotate(int[][] matrix) {
        int size = matrix.length;
        int[][] rotated = new int[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                // Row i becomes column size - 1 - i, read top to bottom.
                rotated[j][size - 1 - i] = matrix[i][j];
            }
        }
        // The caller holds matrix, so change its rows, not just our local name.
        for (int i = 0; i < size; i++) matrix[i] = rotated[i];
    }
}

Big O

Time O(n²)Space O(n²)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines place one value, then put the new rows back. Placing sits inside two loops, one over rows and one over columns. Copying one value is 1 step.

   1. rotated = [[0] * size for _ in range(size)]
   2. for i in range(size):
   3. for j in range(size):
   4. rotated[j][size - 1 - i] = matrix[i][j]
   5. matrix[:] = rotated # copy the rows back

2. 2 Count the runs on Example 1

   Example 1 is 4 × 4, so 16 values. Placing them takes 16 runs. Putting the 4 new rows back into matrix takes 4 more.

   16 + 4 = 20 steps.

   part	place cells	copy rows back
   steps	16	4

   total

   16 + 4 = 20

3. 3 Write the count for any n

   n² (place) + n (rows back) = n² + n

   Check it with Example 1: 16 + 4 = 20.

4. 4 Keep only the part that grows fastest

   Drop the + n. Next to n² it soon stops mattering. What is left is n². Note that n² is also the size of the input, so no answer can be faster: every value must move.

   So the time is O(n²).

5. S Space: count the extra memory the same way

   rotated holds n × n values, a full second grid. The space is O(n²).

   rotated (n × n grid)ij

Transpose, then reverse O(n²), O(1) space

The idea

Two moves in a row give a clockwise turn.

1. Transpose: swap matrix[i][j] with matrix[j][i] for every cell above the diagonal. Now row i holds column i of the original, read top to bottom.
2. Reverse each row. A clockwise turn needs each original column read bottom to top, so flip every row.

Why it is correct: the transpose sends [i][j] to [j][i]. Reversing row j then sends column i to column n − 1 − i. Together, [i][j] ends at [j][size − 1 − i], which is exactly a clockwise turn.

Walkthrough

	c0	c1	c2	c3
r0	10	11	12	13
r1	14	15	16	17
r2	18	19	20	21
r3	22	23	24	25

1. for i in range(size):
2. for j in range(i + 1, size):
3. matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
4. for row in matrix:
5. row.reverse()

Two moves give a clockwise turn: transpose (flip across the main diagonal), then reverse each row. Both work in place.

← BackStep →Play1 / 13

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Transpose, then reverse each row: together they send [i][j] to [j][size - 1 - i].
    // Every cell moves once: O(n^2) time and O(1) extra memory.
    public void rotate(int[][] matrix) {
        int size = matrix.length;
        // j starts above the diagonal, so each pair is swapped once, not twice.
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                int temporary = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temporary;
            }
        }
        // Row i now holds column i top to bottom. Clockwise needs it bottom to top.
        for (int[] row : matrix) {
            for (int left = 0, right = size - 1; left < right; left++, right--) {
                int temporary = row[left];
                row[left] = row[right];
                row[right] = temporary;
            }
        }
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two parts repeat. The transpose swaps one pair per run, inside two loops. The reverse swaps pairs inside each row. One swap is 1 step.

   1. for i in range(size):
   2. for j in range(i + 1, size):
   3. matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
   4. for row in matrix:
   5. row.reverse()

2. 2 Count the runs on Example 1

   Example 1 is 4 × 4. The transpose swaps each pair above the diagonal once: 6 swaps. Each of the 4 rows takes 2 swaps to reverse: 8 swaps.

   6 + 8 = 14 swaps.

   part	transpose	reverse rows
   swaps	6	8

   total

   6 + 8 = 14

3. 3 Write the count for any n

   Above the diagonal there are n × (n − 1) / 2 cells. Each row reverse takes n / 2 swaps:

   n(n − 1)/2 + n × n/2 = n² − n/2

   Check it with Example 1: 16 − 2 = 14.

4. 4 Keep only the part that grows fastest

   Drop the − n/2. What is left is n², the same as the copy, but with no second grid.

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The code keeps only i and j, and the swaps use one temporary value. The space is O(1).

   ij

Common mistake

Swapping the whole grid in the transpose

If j runs over every column instead of starting at i + 1, each pair is swapped twice, and the grid ends up exactly as it started. Only swap the cells above the diagonal.

Tested at the limits

2,000 random grids from 1 x 1 to 6 x 6, odd and even sizes, with many repeated values. Copy to a new grid and transpose, then reverse gave the same answer every time.

Largest inputs	Result
A 20 x 20 grid (the most allowed), every value different. Transpose, then reverse.	Under 0.001 s, and under 0.001 MB of extra memory: swaps in place, no new rows.
The same grid. Copy to a new grid.	Under 0.001 s, and about 0.005 MB: a full second grid of 400 values.