#include <stdio.h>
#include <stdlib.h>

typedef int** Matrix;

Matrix transpose(Matrix mat, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // Swap mat[i][j] and mat[j][i]
            int temp = mat[i][j];
            mat[i][j] = mat[j][i];
            mat[j][i] = temp;
        }
    }
    return mat; // Return the modified matrix
}

// Example usage
int main() {
    int n = 3;

    // Allocate memory for the matrix
    Matrix mat = (Matrix)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        mat[i] = (int*)malloc(n * sizeof(int));
    }

    // Initialize the matrix
    int counter = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            mat[i][j] = counter++;
        }
    }

    // Print the original matrix
    printf("Original matrix:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", mat[i][j]);
        }
        printf("\n");
    }

    // Transpose the matrix in-place
    transpose(mat, n);

    // Print the transposed matrix
    printf("\nTransposed matrix:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", mat[i][j]);
        }
        printf("\n");
    }

    // Free allocated memory
    for (int i = 0; i < n; i++) {
        free(mat[i]);
    }
    free(mat);

    return 0;
}