Start learning free

LESSON 49 OF 319 · MATRIX

Rotate Image in C++: In-Place Transpose and Reverse, O(n²)

Practice O(n^2) Read the full explanation

You get a square grid matrix of integers, with n rows and n columns.

Rotate it a quarter turn clockwise, like turning a photo onto its right side.

matrix is a vector of rows. Each row is a vector of integers. Row 0 is the top row. Column 0 is the leftmost column.

Work in place. Change the numbers inside matrix itself, and don't fill a new grid.

Your function returns nothing. Each example's output shows matrix after the function runs.

 

Example 1:

Input: matrix = [
  [4, 9, 2],
  [3, 5, 7],
  [8, 1, 6]
]
Output: [
  [8, 3, 4],
  [1, 5, 9],
  [6, 7, 2]
]
Explanation: The left column, read from the bottom up, is now the top row.
The top row is now the right column.
The 5 in the center stays where it is.

Example 2:

Input: matrix = [
  [-3, 8],
  [8, 0]
]
Output: [
  [8, -3],
  [0, 8]
]
Explanation: Each number moves to the next corner clockwise:
-3 goes to the top right,
the top-right 8 goes to the bottom right,
0 goes to the bottom left,
the bottom-left 8 goes to the top left.

Example 3:

Input: matrix = [
  [7]
]
Output: [
  [7]
]
Explanation: A single number has nowhere to move.

 

Constraints:

  • n is from 1 to 500.
  • Each value is an integer from -1000 to 1000.
  • Negative values and repeats are allowed.

Note:

Your algorithm should run in O(n2) time and use O(1) extra space: it only moves numbers around inside matrix.

STEP 1 OF 6
    Ctrl + Enter to check

    C++ · MATRIX

    Rotate Image in C++, explained

    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:

    1. Transpose: flip the matrix over its main diagonal (top-left to bottom-right), so the number in row i, column j trades places with the number in row j, column i. Every row becomes the column with the same number.
    2. 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

    1. Store the size matrix.size() in an int named n. The matrix is square, so n is both the row count and the column count.
    2. Loop over the rows with i from 0 while i < n. This starts the transpose.
    3. Loop over the columns to the right of the diagonal with j from i + 1 while j < n. Starting at i + 1 visits each pair of mirror cells once. Starting at 0 would swap each pair twice, and the second swap would undo the first.
    4. Swap matrix[i][j] and matrix[j][i] with swap. That finishes the transpose.
    5. Start a second loop over i from 0 to n - 1, one row at a time.
    6. Reverse the row matrix[i] with reverse, from matrix[i].begin() to matrix[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>> &matrix means 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 cost O(n²) extra space.
    • swap takes references. swap(matrix[i][j], matrix[j][i]) exchanges the two ints stored inside the matrix, without a temporary variable of your own.
    • reverse takes a range. It turns the elements between two iterators around in place. matrix[i] is a reference to the row stored inside matrix, so reversing it changes the matrix.
    • A matrix here is a vector of rows. matrix[i][j] is row i, column j. The rows are separate vectors, but because the matrix is square every row has length n.

    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 j from 0, every pair is swapped twice and the matrix comes back unchanged. For the 3 by 3 example, the result is still 1 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.

    Keep going with C++1,600+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free