Rotate by 90 degree

Given asquare matrix[][]. The task is to rotate it by 90 degrees in clockwise direction without using any extra space.

Examples:

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

Input: mat[][] = [1 2], [3 4]
Output:
3 1 
4 2

Input: mat[][] = [[1]]
Output:
1

Constraints:
1 ≤ mat.size() ≤ 1000
1 <= mat[][] <= 100

Approach 01:

#include <vector>
using namespace std;

void rotate(vector<vector<int>>& matrix) {
    int matrixSize = matrix.size();
    
    for (int layer = 0; layer < matrixSize / 2; ++layer) {
        for (int element = layer; element < matrixSize - layer - 1; ++element) {
            int topLeft = matrix[layer][element];
            
            // Move bottom left to top left
            matrix[layer][element] = matrix[matrixSize - element - 1][layer];
            
            // Move bottom right to bottom left
            matrix[matrixSize - element - 1][layer] = matrix[matrixSize - layer - 1][matrixSize - element - 1];
            
            // Move top right to bottom right
            matrix[matrixSize - layer - 1][matrixSize - element - 1] = matrix[element][matrixSize - layer - 1];
            
            // Move top left (saved in topLeft) to top right
            matrix[element][matrixSize - layer - 1] = topLeft;
        }
    }
}

from typing import List

def rotate(matrix):
    matrixSize = len(matrix)
    
    for layer in range(matrixSize // 2):
        for element in range(layer, matrixSize - layer - 1):
            topLeft = matrix[layer][element]
            
            # Move bottom left to top left
            matrix[layer][element] = matrix[matrixSize - element - 1][layer]
            
            # Move bottom right to bottom left
            matrix[matrixSize - element - 1][layer] = matrix[matrixSize - layer - 1][matrixSize - element - 1]
            
            # Move top right to bottom right
            matrix[matrixSize - layer - 1][matrixSize - element - 1] = matrix[element][matrixSize - layer - 1]
            
            # Move top left (saved in topLeft) to top right
            matrix[element][matrixSize - layer - 1] = topLeft

Time Complexity

• Main Loops:

  The function iterates over each layer of the matrix up to matrixSize / 2 layers. For each layer, it performs a fixed number of swaps proportional to the length of the layer, approximately matrixSize elements. This results in a time complexity of \( O(N^2) \), where \( N \) is the dimension of the matrix, since each element is processed once in the matrix rotation.

• Overall Time Complexity:

  The overall time complexity is \( O(N^2) \), where \( N \) is the size of the matrix (i.e., for an \( N \times N \) matrix).

Space Complexity

• In-place Transformation:

  The function performs all operations in place, meaning it modifies the original matrix without using any extra storage proportional to the input size.

• Auxiliary Variables:

  Only a few variables (matrixSize, layer, element, and topLeft) are used to perform the rotation, which each occupy constant space.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \) since no additional storage is required relative to the input size.