// Efficient Code : Without Using Auxiliary Array

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int n = 4;

	static void swap(int mat[][], int i, int j)
	{
			int temp = mat[i][j];
			mat[i][j] = mat[j][i];
			mat[j][i] = temp;
	}

	static void transpose(int mat[][])
	{

		for(int i = 0; i < n; i++)
			for(int j = i + 1; j < n; j++)
				swap(mat, i, j);
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	transpose(arr);

    		for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < n; j++)
				{
					System.out.print(arr[i][j]+" ");
				}

				System.out.println();
			}	
    } 
}




// Naive Code : 

	static int n = 4;

	static void transpose(int mat[][])
	{
		int temp[][] = new int[n][n];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
              	// copy
				temp[i][j] = mat[j][i]; // temp[i][j] = mat[i][j];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
              	// copy back to original array
				mat[i][j] = temp[i][j];

	}