48 Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up: Could you do this in-place?

The Idea: Replace every row with the nth to last column respectfully. Complexity: O(n) time and O(n) extra space

void rotate(vector<vector<int>>& matrix) {
    int size = matrix.size();
    vector<vector<int>> new_m(size, vector<int>(size));
    // assuming nxn
    int row = size - 1;
    int col = 0;

    for (int i = 0; i < size; i++) {
        // bottom row = first column
        for (int j = 0; j < size; j++) {
            new_m[j][col] = matrix[row][j];
        }
        row--;
        col++;
    }
    matrix = new_m;
}

The Idea: Reverse the matrix, and then swap on the y=-x line of symmetry. ~~Notice that the diagonal swaps with itself, but that's not big deal. ~~We can alternatively reverse each column, and this would have the same effect as reversing the rows. Complexity: O(n) time and O(1) space

void rotate(vector<vector<int>>& matrix) {
    if (matrix.empty()) return;
    reverse(matrix.begin(), matrix.end());
    const size_t rows = matrix.size(), cols = matrix.at(0).size();

    for (int i = 0; i < rows; i++) {
        for (int j = i + 1; j < cols; j++) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
}

Testing

int main() {
    vector<vector<int>> matrix = {
    { 1,2,3,4 },
    { 5,6,7,8 },
    { 9,10,11,12 },
    { 13,14,15,16 },
    };

    rotate(matrix);
    print2d(matrix);
}