Rotate matrix by 90 degrees

The problem, simply

You get an n by n grid of numbers. Turn it 90 degrees clockwise, like turning a photo on a table a quarter turn to the right.

Change the grid you were given. The hard version, and the one interviewers expect, says you may not make a second grid.

A story to remember it

Picture it

Examples

Way 1: the simple way

Make a new empty grid and copy each number to where it belongs after the turn. A number at row i, column j moves to row j, column n - 1 - i. Then copy the new grid back.

1. For every cell (i, j): rotated[j][n - 1 - i] = matrix[i][j].
2. Copy rotated back into matrix.

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] rotated = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                rotated[j][n - 1 - i] = matrix[i][j];   // row i becomes column n - 1 - i

        for (int i = 0; i < n; i++)
            matrix[i] = rotated[i].clone();             // copy back into the given grid
    }
}

How long it takes: every cell is moved once and copied once, O(n^2). Extra room: a whole second grid, O(n^2).

Way 2: the clever way

A turn is two flips, and a flip only swaps pairs, so it needs no second grid.

1. Flip across the main diagonal (this is called the transpose). For every pair i < j, swap matrix[i][j] with matrix[j][i]. Now each old row is a column.
2. Reverse every row. Swap the ends and walk inward.

Why it works: the flip moves (i, j) to (j, i). Reversing the row moves (j, i) to (j, n - 1 - i). Together that is (i, j) to (j, n - 1 - i), the same place as in Way 1.

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        for (int i = 0; i < n; i++) {                 // step 1: flip across the diagonal
            for (int j = i + 1; j < n; j++) {         // j starts at i + 1, so each pair swaps once
                int t = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = t;
            }
        }

        for (int[] row : matrix) {                    // step 2: reverse each row
            for (int l = 0, r = n - 1; l < r; l++, r--) {
                int t = row[l];
                row[l] = row[r];
                row[r] = t;
            }
        }
    }
}

How long it takes: each step touches every cell at most once, O(n^2). Extra room: one temporary number, O(1).

Another way: four cells at a time

You can also turn the grid ring by ring, like turning the outer ring of a combination lock. In each ring, cells come in groups of four (one on each side). Hold one number in your hand, slide the other three one place clockwise, and put the held number down. Every cell moves only once.

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer, last = n - 1 - layer;
            for (int i = first; i < last; i++) {
                int off = i - first;
                int top = matrix[first][i];                              // hold the top one
                matrix[first][i] = matrix[last - off][first];            // left goes to top
                matrix[last - off][first] = matrix[last][last - off];    // bottom goes to left
                matrix[last][last - off] = matrix[i][last];              // right goes to bottom
                matrix[i][last] = top;                                   // top goes to right
            }
        }
    }
}

Same O(n^2) time and O(1) room, with fewer writes (each cell is written once instead of twice). It is easier to get an index wrong, so the two flips are the safer choice under pressure.

Watch out for

• Doing the steps in the other order for clockwise. Reverse rows first, then flip, gives a counter clockwise turn.
• Reversing columns instead of rows after the flip. That also gives counter clockwise.
• A grid that is not square. A 2 by 3 grid turns into a 3 by 2 grid, so it cannot be done in place; make a new grid as in Way 1.

What interviewers ask next

• Counter clockwise? Flip across the diagonal, then reverse each column. Or reverse each row first, then flip.
• 180 degrees? Reverse the order of the rows, then reverse each row. Or turn clockwise twice.
• Turn by k quarter turns? Only k % 4 matters. 0 is nothing, 2 is the 180 turn, 3 is counter clockwise.
• Check whether one grid is a rotation of another. Turn it up to 3 times and compare after each turn, O(n^2).
• Flip across the other diagonal (top right to bottom left)? Swap matrix[i][j] with matrix[n-1-j][n-1-i].

Remember this

Grown-up words: the fold along the diagonal is the transpose, reversing a row is a horizontal reflection, two reflections make a rotation, and the four cell slide is a cyclic swap of the matrix layers.