LeetCode 867: Transpose Matrix

Explanation

To transpose a matrix, we need to flip the matrix over its main diagonal, which means swapping the rows and columns. We can achieve this by iterating through the original matrix and constructing a new transposed matrix. The transposed matrix will have the number of rows equal to the number of columns of the original matrix and vice versa.

• Algorithm:

  1. Initialize a new 2D array to store the transposed matrix with dimensions n x m.
  2. Iterate through each element of the original matrix.
  3. Place the element at position (i, j) in the original matrix to position (j, i) in the transposed matrix.
  4. Return the transposed matrix.

• Time Complexity: O(m * n) where m and n are the dimensions of the original matrix.

• Space Complexity: O(m * n) for the transposed matrix.

class Solution {
    public int[][] transpose(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        int[][] transposed = new int[n][m];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                transposed[j][i] = matrix[i][j];
            }
        }
        
        return transposed;
    }
}