//This is NOT an in-place algorithm
//x' = x*cos(a) - y*sin(b)
//y' = x*sin(a) + y*cos(b)
//With this we rotate around the center of the matrix
//If matrix is n x n. Memory Complexity O(n^2)
//Runtime Complexity O(n^2)
void rotate(vector<vector<int>>& matrix) {
    vector<vector<int>> _matrix = matrix;
    for (int i = 0; i < size(matrix); ++i){
        for (int j = 0; j < size(matrix); ++j){
            matrix[i][j] = _matrix[size(matrix) - 1 - j][i];
        }
    }
}

//This is an in-place algorithm
//If matrix is n x n. Memory Complexity O(1)
//Runtime Complexity O(n^2)
//This is faster because the second for loop iterates as maximum n/2.
void rotate(vector<vector<int>>& matrix) {
    int n = size(matrix);
    for (int i = 0; i < n; ++i){
        for (int j = i + 1; j < n - i; ++j){
            swap(matrix[i][j], matrix[j][n - 1 - i]);
            swap(matrix[i][j], matrix[n - 1 - i][n - 1 - j]);
            swap(matrix[i][j], matrix[n - 1 - j][i]);
        }
    }
}

//This is an in-place algorithm
//If matrix is n x n. Memory Complexity O(1)
//Runtime Complexity O(n^2)
void rotate(vector<vector<int>>& matrix) {
    int n = size(matrix);
    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()); //O(n)
    }
}