Chapter 1 - Problem 7 - Rotate Matrix

Problem

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Solution

We start swapping index by index, moving the left to the top, the bottom to the left, and so on.
We start from the outermost layer and working our way inwards.

EXAMPLE

A very good explanation:

Solution in C++

bool rotateMatrixvector<int>>& matrix {
    if (matrix.size() != matrix.at(0).size()) return false;
    int n = matrix.size();
    int totNumOfLevels = n / 2;
    int last = n - 1;

    for (int level = 0; level < totNumOfLevels; level++) {
        for(int i = level; i < last; i++) {
            int top = matrix[level][i];

            //left -> top
            matrix[level][i] = matrix[last - i + level][level];

            //bottom -> left
            matrix[last - i + level][level] = matrix[last][last - i + level];
            
            //right -> bottom
            matrix[last][last - i + level] = matrix[i][last];

            //top -> right
            matrix[i][last] = top;
        }
        last--;
    }
    return true;
}

• Time complexity: $O(N^2)$ (the best we can do since any algorithm must touch all $N^2$ elements)
• Space complexity: $O(1)$