Problem overview
The method rotate receives a square matrix, a vector<vector<int>> with n rows and n columns, and turns it a quarter turn clockwise. It must do this in place: the numbers move inside matrix itself, nothing is returned, and no second matrix is built.
For this matrix:
1 2 3
4 5 6
7 8 9
the rotated result is:
7 4 1
8 5 2
9 6 3
The left column read from the bottom up (7, 4, 1) becomes the top row, and the top row (1, 2, 3) becomes the right column. The statement asks for O(n²) time, which is the size of the matrix, and O(1) extra space.
Approach: two simple flips make one rotation
The easy way to rotate is to build a new matrix and copy each value to its new position: the value at row i, column j goes to row j, column n - 1 - i. That uses O(n²) extra space, which the statement rules out. Doing the same moves in place is tricky, because writing to a cell destroys a value you haven't moved yet.
The trick is to split the rotation into two operations that are each easy to do in place:
- Transpose: flip the matrix over its main diagonal (top-left to bottom-right), so the number in row
i, columnjtrades places with the number in rowj, columni. Every row becomes the column with the same number. - Reverse every row.
After the transpose, row 0 of the example is 1 4 7, which is the first column read from the top. A clockwise quarter turn needs that column read from the bottom up, so reversing the row gives 7 4 1, the first row of the answer.
After the transpose, the example looks like this:
1 4 7
2 5 8
3 6 9
Reversing each row then gives the rotated matrix shown above.
Step by step
- Store the size
matrix.size()in anintnamedn. The matrix is square, sonis both the row count and the column count. - Loop over the rows with
ifrom 0 whilei < n. This starts the transpose. - Loop over the columns to the right of the diagonal with
jfromi + 1whilej < n. Starting ati + 1visits each pair of mirror cells once. Starting at 0 would swap each pair twice, and the second swap would undo the first. - Swap
matrix[i][j]andmatrix[j][i]withswap. That finishes the transpose. - Start a second loop over
ifrom 0 ton - 1, one row at a time. - Reverse the row
matrix[i]withreverse, frommatrix[i].begin()tomatrix[i].end().
The solution in C++
class 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 (int i = 0; i < n; i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
}
};
The C++ details worth knowing:
- The parameter is a reference.
vector<vector<int>> &matrixmeans the function works on the caller's matrix. Without the&, the function would receive a copy, rotate the copy, and leave the original unchanged. The copy would also costO(n²)extra space. swaptakes references.swap(matrix[i][j], matrix[j][i])exchanges the twoints stored inside the matrix, without a temporary variable of your own.reversetakes a range. It turns the elements between two iterators around in place.matrix[i]is a reference to the row stored insidematrix, so reversing it changes the matrix.- A matrix here is a vector of rows.
matrix[i][j]is rowi, columnj. The rows are separate vectors, but because the matrix is square every row has lengthn.
Complexity
Time is O(n²). The transpose loops visit about half of the n² cells and do one swap for each. The row reversal touches every cell once. Together that is a constant multiple of n², which is optimal because every cell has to be looked at.
Extra space is O(1). Besides n, the loop counters and the temporary inside swap, nothing is allocated.
Edge cases and common mistakes
- A 1 by 1 matrix.
{{7}}stays{{7}}. The inner loop never runs, and reversing a single-element row does nothing. - A 2 by 2 matrix.
{{1, 2}, {3, 4}}becomes{{3, 1}, {4, 2}}. - Starting the inner loop at 0. With
jfrom 0, every pair is swapped twice and the matrix comes back unchanged. For the 3 by 3 example, the result is still1 2 3 / 4 5 6 / 7 8 9. - Swapping in the wrong order of flips. Reversing the rows first and then transposing turns the matrix counter-clockwise, not clockwise.
- Reversing the whole matrix instead of each row. Reversing the order of the rows flips the matrix upside down; it doesn't read each column backwards. Reverse every
matrix[i]separately. - Odd sizes. The centre cell of an odd matrix sits on the diagonal and is never swapped. That is correct, since it stays in place under a rotation.
Testing
The 4 by 4 matrix {{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}} becomes:
15 13 2 5
14 3 4 1
12 6 8 9
16 7 10 11
The corners show the quarter turn: 5 moves to the top-right, 11 to the bottom-right, 16 to the bottom-left and 15 to the top-left.
