Transpose of Matrix

JavaView on GFG

Time: O(n^2)

Space: O(1)

Intuition

Transpose: swap matrix[i][j] and matrix[j][i] for all i < j.

Algorithm

1For i in 0..n-1: for j in i+1..n-1: swap(matrix[i][j], matrix[j][i]).

Common Pitfalls

•Only swap upper triangle to avoid double-swapping. For non-square: create new matrix.

Transpose of Matrix.java

Java

// Approach: Swap elements at (i,j) and (j,i) for all i < j to transpose in-place.
// Time: O(n^2) Space: O(1)
import java.util.*;

class Solution {
    public ArrayList<ArrayList<Integer>> transpose(int[][] mat) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();

        for (int i = 0; i < mat.length; i++) {
            ArrayList<Integer> temp = new ArrayList<>();
            for (int j = 0; j < mat[0].length; j++)
                temp.add(mat[j][i]);
            list.add(temp);
        }

        return list;
    }
}

Was this solution helpful?