Rotation of Matrix (90 Degrees Clockwise)

import sys

def rotateMatrix_optimal(matrix):
    """O(N^2) Time, O(1) Space - Transpose then Reverse"""
    N = len(matrix)

    # 1. Transpose: Swap matrix[i][j] with matrix[j][i]
    for i in range(N):
        for j in range(i + 1, N):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # 2. Reverse each row
    for i in range(N):
        matrix[i].reverse()

def rotateMatrix_brute(matrix):
    """O(N^2) Time, O(N^2) Space - Brute Force (Extra Space)"""
    N = len(matrix)
    rotated = [[0] * N for _ in range(N)]

    for i in range(N):
        for j in range(N):
            # Rotation rule: rotated[j][N - 1 - i] = matrix[i][j]
            rotated[j][N - 1 - i] = matrix[i][j]
            
    return rotated

# The platform reading logic needs to handle multiple test cases (T) and N.

import java.util.Scanner;
import java.util.Collections;
import java.util.Arrays;

class Solution {

    // O(N^2) Time, O(1) Space - Optimal: Transpose then Reverse
    public static void rotateMatrix_optimal(int[][] matrix) {
        int N = matrix.length;

        // 1. Transpose: Swap matrix[i][j] with matrix[j][i]
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // 2. Reverse each row
        for (int i = 0; i < N; i++) {
            // Use a two-pointer approach for in-place reversal
            int left = 0;
            int right = N - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++;
                right--;
            }
        }
    }

    // O(N^2) Time, O(N^2) Space - Brute Force (Extra Space)
    public static int[][] rotateMatrix_brute(int[][] matrix) {
        int N = matrix.length;
        int[][] rotated = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // Rotation rule: rotated[j][N - 1 - i] = matrix[i][j]
                rotated[j][N - 1 - i] = matrix[i][j];
            }
        }
        return rotated;
    }
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// O(N^2) Time, O(1) Space - Optimal: Transpose then Reverse
void rotateMatrix_optimal(vector<vector<int>>& matrix) {
    int N = matrix.size();

    // 1. Transpose (Swap A[i][j] with A[j][i])
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }

    // 2. Reverse each row
    for (int i = 0; i < N; ++i) {
        reverse(matrix[i].begin(), matrix[i].end());
    }
}

// O(N^2) Time, O(N^2) Space - Brute Force (Extra Space)
vector<vector<int>> rotateMatrix_brute(const vector<vector<int>>& matrix) {
    int N = matrix.size();
    vector<vector<int>> rotated(N, vector<int>(N));

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            // New row index is old column index (j)
            // New column index is N - 1 - old row index (i)
            rotated[j][N - 1 - i] = matrix[i][j];
        }
    }
    return rotated;
}