C++: Rotate Image

Thought Process

The problem requires rotating an n x n matrix by 90 degrees clockwise. We achieve this in two steps: First, we transpose the matrix, which swaps elements across the diagonal. Second, we reverse each row of the transposed matrix to complete the rotation. This approach ensures the rotation is done in-place without using extra space. For rotating 90 degrees counter-clockwise, we would reverse the rows first and then transpose the matrix. 

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        
        int rows = matrix.size();
        int cols = matrix[0].size();

        // Transform the matrix
        for(int i=0;i<rows;i++){
            for(int j=i;j<cols;j++){
                swap(matrix[i][j],matrix[j][i]);
            }
        }
        
        // Reverse the matrix, row wise.
        for(int i=0;i<rows;i++)
            reverse(matrix[i].begin(),matrix[i].end());

        // Note: For rotating ACW, first reverse & then transform it.
    }
};

Code Complexity

Time Complexity: O(n2)

The algorithm iterates through each element of the matrix once, resulting in a time complexity of O(n2), where n is the number of rows/columns in the matrix.

Space Complexity: O(1)

The algorithm performs the rotation in-place, using only a constant amount of extra space.

Code copied!