Rotate Image

Problem

Given a square n x n matrix of integers matrix, rotate it by 90 degrees clockwise.

You must rotate the matrix in-place. Do not allocate another 2D matrix and do the rotation.

Examples

Example 1:

Input: matrix = [
  [1,2],
  [3,4]
]

Output: [
  [3,1],
  [4,2]
]

Example 2:

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

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

Constraints

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

You should aim for a solution with O(n^2) time and O(1) space, where n is the length of the side of the given square matrix.

Solution

A rotation clockwise is a transpose then flip along x-axis. A rotation counter-clockwise is a transpose then flip along y-axis. Both a transpose and a flip can be done in-place.

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        const auto ROWS = matrix.size();
        const auto COLS = matrix[0].size();
        // A rotation clockwise is the same as a transpose and flip along x-axis
        // A rotation counter-clockwise is a transpose and flip along y-axis
 
        // In-place transpose
        for (int r = 0; r < ROWS; ++r) {
            for (int c = r + 1; c < COLS; ++c) {
                std::swap(matrix[r][c], matrix[c][r]);
            }
        }
 
        // In-place flip along x-axis
        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS / 2; ++c) {
                std::swap(matrix[r][c], matrix[r][COLS - c - 1]);
            }
        }
    }
};