Transpose a Matrix : Program 0(1) space

Problem statement: Transpose a Matrix.

Given a matrix, your task is to find its transpose of the given matrix.

Transpose: The transpose of a matrix means, interchanging its rows into columns or columns into rows.

Examples:

Example 1:
Input:      {{4,5,6},
             {7,8,9},
             {10,11,12}}
Output: 
              4 7 10 
              5 8 11 
              6 9 12 

Explanation: The 1st row i.e 4,5,6 and 1st column i.e 4,7,10 
are interchanged in the same way other rows and columns 
will also interchange their values.

Example 2:
Input:   {{1,2,3}
          {4,5,6},
          {7,8,9},
          {10,11,12}}
Output:
        1 4 7 10 
        2 5 8 11 
        3 6 9 12 

Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Brute force

Intuition:

By observing the question it is clear that the elements at 1st row are interchanged with 1st column, and the elements at 2nd row are interchanged with the 2nd column and so on…which means the element at index 0,1 is interchanging with the elements at the index 1,0 and 0,2  is interchanging with 2,0 and so on…, So to achieve this we can use another matrix to store its corresponding values.

Approach:

  • Create a new matrix(say temp) to store new values.
  • Transverse through the entire matrix and while traversing interchange the rows and columns

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
#define N 3

void transpose(int matrix[][N]) {

        int temp[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                temp[i][j] = matrix[j][i];
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cout<<temp[i][j]<<" ";
            }
            cout<<endl;
        }      
    }

int main() {
        // matrix initialization
        int matrix[3][3]=  { {4,5,6}, {7,8,9}, {10,11,12}};
       
        transpose(matrix);

        // printing matrix  
    }

Output:

4 7 10
5 8 11
6 9 12

Time complexity: O(n*m) for traversing

Space complexity: O(n*m) for new matrix

Java Code

public class TransposeOfMatrix {
    public static void main(String[] args) {

        // matrix initialization
        int matrix[][] =  { {4,5,6}, {7,8,9}, {10,11,12}};
        int m = matrix.length;
        int n = matrix[0].length;

        int temp[][] = transpose(matrix,m,n);

        // printing matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(temp[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static int[][] transpose(int[][] matrix,int m,int n) {

        // creating new matrix to store transpose
        /* Creating temp matrix of size [n][m] so 
           that it will work for rectangle matrix also*/
        int temp[][] = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                temp[i][j] = matrix[j][i];
            }
        }

        return temp;
    }
}

Output:

4 7 10
5 8 11
6 9 12

Time complexity: O(n*m) for traversing

Space complexity: O(n*m) for new matrix

Solution 2: In-place

Intuition:

From the definition of transpose it is known that transposing of a matrix is interchanging the rows and columns, so to achieve this, we can directly interchange elements without using extra space.

Approach:

  1. Traverse through the entire matrix
  2. Swap row and corresponding column elements

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
#define N 3

void transpose(int matrix[][N]) {

        int temp[N][N];

         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;
                    }
                }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cout<<matrix[i][j]<<" ";
            }
            cout<<endl;
        }
    }

int main() {

        // matrix initialization
        int matrix[3][3]=  { {4,5,6}, {7,8,9}, {10,11,12}};
       
        transpose(matrix);

        // printing matrix
        
    }

Output:

4 7 10
5 8 11
6 9 12

Time complexity: O(n*m) for traversing

Space complexity: O(1)

Java Code

public class TransposeOfMatrix {
    public static void main(String[] args) {

        //matrix initialization
        int matrix[][] =  { {4,5,6}, {7,8,9}, {10,11,12}};
        int m = matrix.length;
        int n = matrix[0].length;

      transpose(matrix,m,n);

        //printing matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static void transpose(int[][] matrix,int m,int n) {

                for (int i=0;i<n;i++){
                    for (int j=i+1;j<m;j++){
                        int temp = matrix[i][j];
                        matrix[i][j] = matrix[j][i];
                        matrix[j][i] = temp;
                    }
                }

    }
}

Output:

4 7 10
5 8 11
6 9 12

Time complexity: O(n*m) for traversing

Space complexity: O(1)

Special thanks to Sai bargav Nellepalli for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article