Program to find transpose of a matrix

Given a 2D matrix mat[][], compute its transpose. The transpose of a matrix is formed by converting all rows of mat[][] into columns and all columns into rows.

Example:

Input: mat[][] = [[1, 1, 1, 1],
[2, 2, 2, 2],
[3, 3, 3, 3],
[4, 4, 4, 4]]
Output: [[1, 2, 3 ,4],
[1, 2, 3, 4],
[1, 2, 3, 4],
[1, 2, 3, 4]]
Explanation: The output is the transpose of the input matrix, where each row becomes a column. This rearranges the data so that vertical patterns in the original matrix become horizontal in the result.

Input: mat[][] = [[1, 2],
[9, -2]]
Output: [[1, 9],
[2, -2]]
Explanation: The output is the transpose of the input matrix, where each row becomes a column. This rearranges the data so that vertical patterns in the original matrix become horizontal in the result.

[Approach 1] Brute Force Matrix Transposition O(n*m) Time and O(n*m) Space

The idea is to create a new matrix where rows become columns by swapping indices — element at position [i][j] in the original becomes [j][i] in the transposed matrix.

Step by Step Implementations:

• Initialize a new matrix of size m × n (rows become columns and vice versa).
• Iterate through each element of the original matrix.
• Assign each element from row r and column c in the original matrix to row c and column r in the new matrix.
• Return the new transposed matrix.

#include <iostream> #include <vector> using namespace std; vector<vector<int>> transpose(vector<vector<int>>& mat) {  int rows = mat.size();   int cols = mat[0].size();     // Create a result matrix of size   // cols x rows for the transpose  vector<vector<int>> tMat(cols, vector<int>(rows));  // Fill the transposed matrix  // by swapping rows with columns  for (int i = 0; i < rows; i++) {  for (int j = 0; j < cols; j++) {    // Assign transposed value  tMat[j][i] = mat[i][j];   }  }  return tMat;  } int main() {  vector<vector<int>> mat = {  {1, 1, 1, 1},  {2, 2, 2, 2},  {3, 3, 3, 3},  {4, 4, 4, 4}  };  vector<vector<int>> res = transpose(mat);  for (auto& row : res) {  for (auto& elem : row) {  cout << elem << ' ';   }  cout << "\n";   }  return 0; } 

import java.util.ArrayList; import java.util.Scanner; public class GfG {  public static ArrayList<ArrayList<Integer>>  transpose(int[][] mat) {    int rows = mat.length;   int cols = mat[0].length;   // Create a result matrix of size   // cols x rows for the transpose  ArrayList<ArrayList<Integer>> tMat = new ArrayList<>();  // Fill the transposed matrix by   // swapping rows with columns  for (int i = 0; i < cols; i++) {  ArrayList<Integer> row = new ArrayList<>();  for (int j = 0; j < rows; j++) {  // Assign transposed value  row.add(mat[j][i]);   }  tMat.add(row);  }  return tMat;  }  public static void main(String[] args) {  int[][] mat = {  {1, 1, 1, 1},  {2, 2, 2, 2},  {3, 3, 3, 3},  {4, 4, 4, 4}  };  ArrayList<ArrayList<Integer>> res = transpose(mat);  for (ArrayList<Integer> row : res) {  for (int elem : row) {  System.out.print(elem + " ");  }  System.out.println();  }  } } 

def transpose(mat): rows = len(mat) cols = len(mat[0]) # Create a result matrix of size # cols x rows for the transpose tMat = [[0 for _ in range(rows)] for _ in range(cols)] # Fill the transposed matrix by # swapping rows with columns for i in range(rows): for j in range(cols): # Assign transposed value tMat[j][i] = mat[i][j] return tMat if __name__ == "__main__": mat = [[1, 1, 1, 1],[2, 2, 2, 2],[3, 3, 3, 3], [4, 4, 4, 4]] res = transpose(mat) for row in res: for elem in row: print(elem, end=' ') print() 

using System; using System.Collections.Generic; public class GfG {  public static List<List<int>> transpose(int[,] mat) {  int rows = mat.GetLength(0);   int cols = mat.GetLength(1);   // Create a result matrix of size   // cols x rows for the transpose  List<List<int>> tMat = new List<List<int>>();  // Fill the transposed matrix by   // swapping rows with columns  for (int j = 0; j < cols; j++) {  List<int> row = new List<int>();  for (int i = 0; i < rows; i++) {    // Assign transposed value  row.Add(mat[i, j]);  }  tMat.Add(row);  }  return tMat;   }  public static void Main()  {  int[,] mat = {  {1, 1, 1, 1},  {2, 2, 2, 2},  {3, 3, 3, 3},  {4, 4, 4, 4}  };  List<List<int>> res = transpose(mat);  int rows = res.Count;  int cols = res[0].Count;  for (int i = 0; i < rows; i++)  {  for (int j = 0; j < cols; j++)  {  Console.Write(res[i][j] + " ");  }  Console.WriteLine();  }  } } 

function transpose(mat) {  const rows = mat.length;   const cols = mat[0].length;   // Create a result matrix of size  // cols x rows for the transpose  const tMat = new Array(cols).fill(0).map(() =>  new Array(rows).fill(0));  // Fill the transposed matrix by  // swapping rows with columns  for (let i = 0; i < rows; i++) {  for (let j = 0; j < cols; j++) {    // Assign transposed value  tMat[j][i] = mat[i][j];  }  }  return tMat;  } // Driver Code const mat = [[1, 1, 1, 1],[2, 2, 2, 2],[3, 3, 3, 3], [4, 4, 4, 4]]; const res = transpose(mat); for (const row of res) {  console.log(row.join(" ")); } 

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 

[Approach 2] Using constant space for Square Matrix O(n*n) Time and O(1) Space

This approach works only for square matrices, where the number of rows is equal to the number of columns. It is called an in-place algorithm because it performs the transposition without using any extra space.

Step by Step Implementations:

• Initialize two nested loops:
  • Outer loop: i from 0 to n-1
  • Inner loop: j from i+1 to n-1
    This avoids diagonal and already swapped positions.
• Swap elements:
  • For each pair (i, j), swap mat[i][j] with mat[j][i]
  • This mirrors the elements across the main diagonal.
• Continue until all such upper-triangle elements are swapped with their lower-triangle counterparts.

#include <iostream> #include <vector>  using namespace std; vector<vector<int>> transpose(vector<vector<int>>& mat) {  int n = mat.size();   // Traverse the upper triangle of the matrix  for (int i = 0; i < n; i++) {  for (int j = i + 1; j < n; j++) {    // Swap elements across the diagonal  swap(mat[i][j], mat[j][i]);  }  }  return mat;  } int main() {    vector<vector<int>> mat = {  {1, 1, 1, 1},  {2, 2, 2, 2},  {3, 3, 3 ,3},  {4, 4, 4, 4}  };  vector<vector<int>> res = transpose(mat);  for (const auto& row : res) {  for (int elem : row) {  cout << elem << " ";   }  cout << endl;   }  return 0; } 

import java.util.Arrays; class GfG {  public static int[][] transpose(int[][] mat) {  int n = mat.length;  // Traverse the upper triangle of the matrix  for (int i = 0; i < n; i++) {  for (int j = i + 1; j < n; j++) {  // Swap elements across the diagonal  int temp = mat[i][j];  mat[i][j] = mat[j][i];  mat[j][i] = temp;  }  }  return mat;  }  public static void main(String[] args) {  int[][] mat = {  {1, 1, 1, 1},  {2, 2, 2, 2},  {3, 3, 3, 3},  {4, 4, 4, 4}  };  int[][] res = transpose(mat);  for (int[] row : res) {  for (int elem : row) {  System.out.print(elem + " ");  }  System.out.println();  }  } } 

def transpose(mat): # Number of rows (and columns, since it's square) n = len(mat) # Traverse the upper triangle of the matrix  for i in range(n): for j in range(i + 1, n): # Swap elements across the diagonal mat[i][j], mat[j][i] = mat[j][i], mat[i][j] return mat if __name__ == "__main__": mat = [[1, 1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3], [4, 4, 4, 4]] res = transpose(mat) for row in res: print(" ".join(map(str, row))) 

using System; using System.Collections.Generic; public class GfG {  public static List<List<int>> transpose(int[,] mat) {    // Number of rows and columns  int rows = mat.GetLength(0);  int cols = mat.GetLength(1);  List<List<int>> result = new List<List<int>>();  // Build the transposed matrix  for (int j = 0; j < cols; j++) {  List<int> row = new List<int>();  for (int i = 0; i < rows; i++) {  row.Add(mat[i, j]);  }  result.Add(row);  }  return result;   }  public static void Main() {  int[,] mat = {  {1, 1, 1, 1},  {2, 2, 2, 2},  {3, 3, 3 ,3},  {4, 4, 4, 4}  };    List<List<int>> res = transpose(mat);   int rows = res.Count;  int cols = res[0].Count;  for (int i = 0; i < rows; i++) {  for (int j = 0; j < cols; j++) {  Console.Write(res[i][j] + " ");  }  Console.WriteLine();  }  } } 

function transpose(mat) {     // Number of rows (and columns, since it's square)  const n = mat.length;  // Traverse the upper triangle of the matrix  for (let i = 0; i < n; i++) {  for (let j = i + 1; j < n; j++) {    // Swap elements across the diagonal  let temp = mat[i][j];  mat[i][j] = mat[j][i];  mat[j][i] = temp;  }  }  return mat;  } // Driver code const mat = [[1, 1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3], [4, 4, 4, 4]]; const res = transpose(mat);  for (const row of res) {  console.log(row.join(" ")); } 

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4