Rotate Image

You are given a square grid of integers matrix with n rows and n columns, for example the pixels of a square picture.

Turn the grid a quarter turn clockwise (90 degrees). After the turn, the first row of the original grid must become the last column, the second row the second-to-last column, and so on.

Do the rotation in place: change matrix itself instead of building and returning a second grid. Your function does not need to return anything; the judge inspects matrix after your function finishes.

Example 1

Example 2

Example 3

Constraints

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

Pattern Path · Math, Bits & Strings · problem 39 of 169

Start simple

Copy every cell into a new n by n grid at its rotated position and copy the result back: O(n²) time but O(n²) extra space, which breaks the in-place requirement.

The key idea

A clockwise quarter turn sends the cell at (r, c) to (c, n - 1 - r). Doing that directly in place is awkward, because writing a value overwrites another value you still need.

Split the move into two steps that are each made of simple swaps:

• Transpose: swap matrix[r][c] with matrix[c][r] for every c > r. Now the cell from (r, c) sits at (c, r).
• Mirror each row: reverse every row, which moves column j to column n - 1 - j. The cell that was at (c, r) lands on (c, n - 1 - r), exactly the rotated position.

Each swap exchanges two values, so nothing is lost and no extra grid is needed. Only the upper triangle is visited during the transpose; visiting both triangles would swap every pair twice and undo the work.

An equivalent approach rotates the grid layer by layer, cycling four cells at a time. It does the same work but its index arithmetic is easier to get wrong.

Complexity

• Time: O(n²)
• Space: O(1)

Python

class Solution:
    def rotate(self, matrix):
        n = len(matrix)
        # Step 1: transpose (flip across the main diagonal).
        for r in range(n):
            for c in range(r + 1, n):
                matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
        # Step 2: mirror every row left-to-right.
        for row in matrix:
            row.reverse()

JavaScript

var rotate = function(matrix) {
  const n = matrix.length;
  // Step 1: transpose (flip across the main diagonal).
  for (let r = 0; r < n; r++) {
    for (let c = r + 1; c < n; c++) {
      [matrix[r][c], matrix[c][r]] = [matrix[c][r], matrix[r][c]];
    }
  }
  // Step 2: mirror every row left-to-right.
  for (const row of matrix) row.reverse();
};

What the interviewer is checking

The interviewer wants to see you derive the index mapping carefully and spot that a hard transformation can be composed from two easy in-place ones.

Mistakes to avoid

• Transposing over the full grid instead of one triangle, which swaps each pair twice and leaves the grid unchanged.
• Reversing the columns (or the row order) instead of each row, which produces a counter-clockwise turn.
• Allocating a new grid and reassigning the local variable, which leaves the caller's grid untouched.
• Off-by-one errors in the layer-by-layer version for odd n, where the centre cell must stay where it is.

Follow-ups to expect

• How would you rotate counter-clockwise? (Transpose, then reverse the row order.)
• What about a 180 degree turn? (Reverse rows, then reverse each row.)
• What if the grid is not square? (Needs a new n by m grid.)

In real software

Image editors and phone cameras rotate pictures this way, and graphics code rotates tiles and sprites with the same transpose-and-flip trick.

Practice next