Solution Explanation for Transpose Matrix

The problem asks to create a transposed matrix from a given matrix. The transpose of a matrix is obtained by interchanging its rows and columns. For example, if the input matrix is:

[[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]]

The transposed matrix would be:

[[1, 4, 7],
 [2, 5, 8],
 [3, 6, 9]]

Approach: Simulation

The most straightforward approach is to iterate through the input matrix and create a new matrix with the rows and columns swapped. This is done by directly assigning values from the input matrix to the correct positions in the new matrix.

Code Implementations

The following code implements this approach in various programming languages:

Python

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        m = len(matrix)
        n = len(matrix[0])
        result = [[0] * m for _ in range(n)] # Initialize result matrix with 0s.  Dimensions are swapped.
        for i in range(m):
            for j in range(n):
                result[j][i] = matrix[i][j] # Swap row and column indices
        return result
 

This Python code first initializes a result matrix with dimensions swapped compared to the input. Then, it iterates through the input matrix, assigning each element matrix[i][j] to result[j][i], effectively transposing the matrix.

Java

class Solution {
    public int[][] transpose(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] result = new int[n][m];  //Dimensions are swapped
 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[j][i] = matrix[i][j]; // Swap row and column indices
            }
        }
        return result;
    }
}

The Java code mirrors the Python logic, creating a new result matrix with dimensions swapped and then populating it by swapping indices during iteration.

C++

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> result(n, vector<int>(m)); //Dimensions are swapped
 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[j][i] = matrix[i][j];  //Swap row and column indices
            }
        }
        return result;
    }
};

Similar to Python and Java, the C++ code transposes the matrix by iterating and swapping indices.

JavaScript

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var transpose = function(matrix) {
    let rows = matrix.length;
    let cols = matrix[0].length;
    let result = Array.from({length: cols}, () => new Array(rows).fill(0)); // Dimensions swapped
 
    for(let i=0; i<rows; i++){
        for(let j=0; j<cols; j++){
            result[j][i] = matrix[i][j]; // Swap row and column indices
        }
    }
    return result;
};

JavaScript code also follows the same approach, using Array.from for creating the transposed matrix and then populating it by iterating and swapping indices.

Time and Space Complexity Analysis

• Time Complexity: O(m*n), where 'm' is the number of rows and 'n' is the number of columns in the input matrix. This is because we iterate through each element of the matrix once.

• Space Complexity: O(mn). We create a new matrix of size mn to store the transposed matrix. The space used is proportional to the size of the input matrix. Ignoring the output matrix, the space complexity is O(1).