# Transpose Matrix
**Difficulty:** EASY
[External](https://leetcode.com/problems/transpose-matrix)
Canonical: https://scaleengineer.com/dsa/problems/transpose-matrix
**Data structures:** Array, Matrix
**Companies:** [ConsultAdd](https://scaleengineer.com/companies/consultadd), [Verkada](https://scaleengineer.com/companies/verkada)
---
## Problem
Given a 2D integer array `matrix`, return _the **transpose** of_ `matrix`.

The **transpose** of a matrix is the matrix flipped over its main diagonal, switching the matrix's row and column indices.

![](https://assets.glich.co/dsa/transpose-matrix/image0.png)

**Example 1:**

**Input:** matrix = [[1,2,3],[4,5,6],[7,8,9]]
**Output:** [[1,4,7],[2,5,8],[3,6,9]]

**Example 2:**

**Input:** matrix = [[1,2,3],[4,5,6]]
**Output:** [[1,4],[2,5],[3,6]]

**Constraints:**

* `m == matrix.length`
* `n == matrix[i].length`
* `1 <= m, n <= 1000`
* `1 <= m * n <= 105`
* `-109 <= matrix[i][j] <= 109`

# Approaches
## Simulation with a New Matrix
The most straightforward and optimal approach is to directly construct the transposed matrix based on its definition. The transpose of a matrix is formed by turning all the rows of a given matrix into columns and vice-versa. This means the element at row `i` and column `j` in the original matrix moves to row `j` and column `i` in the new matrix. This approach creates a new matrix with swapped dimensions and fills it by iterating through the original matrix.
**Time:** O(R * C), where `R` is the number of rows and `C` is the number of columns. We need to iterate through each of the `R * C` elements of the matrix once to perform the transposition. · **Space:** O(R * C), where `R` is the number of rows and `C` is the number of columns. We create a new matrix of size `C x R` to store the result. The space required is proportional to the number of elements in the matrix.
**Pros:** Simple to understand and implement.; Works for any `m x n` matrix, including square and non-square matrices.; Optimal in terms of time complexity, as every element must be visited.
**Cons:** Requires extra space proportional to the size of the matrix. This is unavoidable for non-square matrices where the dimensions change.
### Explanation
This method involves creating a new matrix with dimensions `n x m`, where the original matrix has dimensions `m x n`. We then iterate through each element of the original matrix and place it in its new position in the transposed matrix.

Here's the step-by-step algorithm:

1.  Determine the dimensions of the input `matrix`. Let's say it has `R` rows and `C` columns.
2.  Create a new result matrix, `transposedMatrix`, with dimensions `C x R`.
3.  Iterate through the original `matrix` with two nested loops. The outer loop runs from `r = 0` to `R-1` (for rows), and the inner loop runs from `c = 0` to `C-1` (for columns).
4.  For each element `matrix[r][c]`, assign it to the corresponding position in the new matrix: `transposedMatrix[c][r] = matrix[r][c]`.
5.  After the loops complete, the `transposedMatrix` will hold the transposed version of the input `matrix`. Return `transposedMatrix`.

For example, if `matrix[0][1]` is `2`, it will be placed at `result[1][0]`.

```java
class Solution {
    public int[][] transpose(int[][] matrix) {
        int R = matrix.length;
        if (R == 0) {
            return new int[0][0];
        }
        int C = matrix[0].length;
        
        int[][] transposedMatrix = new int[C][R];
        
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                transposedMatrix[c][r] = matrix[r][c];
            }
        }
        
        return transposedMatrix;
    }
}
```
### Algorithm
1. Get the dimensions of the input `matrix`: `R` rows and `C` columns.
2. Create a new result matrix, `transposedMatrix`, with dimensions `C` rows and `R` columns.
3. Iterate through the original `matrix` using nested loops. The outer loop iterates through rows `r` from `0` to `R-1`, and the inner loop iterates through columns `c` from `0` to `C-1`.
4. In each iteration, copy the element `matrix[r][c]` to `transposedMatrix[c][r]`.
5. After the loops complete, return the `transposedMatrix`.

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @param {number[][]} matrix * @return {number[][]} */ var transpose = function ( matrix ) { const m = matrix . length ; const n = matrix [ 0 ]. length ; const ans = new Array ( n ). fill ( 0 ). map (() => new Array ( m ). fill ( 0 )); for ( let i = 0 ; i < n ; ++ i ) { for ( let j = 0 ; j < m ; ++ j ) { ans [ i ][ j ] = matrix [ j ][ i ]; } } return ans ; };
```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> transpose(vector<vector<int>> &matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> ans(n, vector<int>(m));
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j)
        ans[i][j] = matrix[j][i];
    return ans;
  }
};

```

### Python

```python
class Solution:
    def transpose(self, matrix: List[List[int]]
                  ) -> List[List[int]]: return list(zip(* matrix))

```