# LeetCode 867: Transpose Matrix

## Problem Restatement

We are given a 2D integer array `matrix`.

We need to return its transpose.

The transpose of a matrix is created by switching rows and columns.

If an element is at:

```python
matrix[row][col]
```

then in the transposed matrix it goes to:

```python
answer[col][row]
```

So the value at row `r`, column `c` becomes the value at row `c`, column `r`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A 2D integer array `matrix` |
| Output | The transposed matrix |
| Rule | `matrix[r][c]` becomes `answer[c][r]` |

Function shape:

```python
class Solution:
    def transpose(self, matrix: list[list[int]]) -> list[list[int]]:
        ...
```

## Examples

Example 1:

```python
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
```

The first row becomes the first column:

```python
[1, 2, 3] -> [1, 2, 3] as column values
```

The result is:

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

Example 2:

```python
matrix = [
    [1, 2, 3],
    [4, 5, 6],
]
```

This is a `2 x 3` matrix.

After transposition, it becomes a `3 x 2` matrix:

```python
[
    [1, 4],
    [2, 5],
    [3, 6],
]
```

## First Thought: Create a New Matrix

A square matrix can sometimes be transposed in place by swapping across the main diagonal.

But this problem allows rectangular matrices.

For example, a `2 x 3` matrix becomes a `3 x 2` matrix.

Because the shape can change, the clean approach is to create a new matrix with swapped dimensions.

If the original matrix has:

```python
rows = len(matrix)
cols = len(matrix[0])
```

then the answer should have:

```python
cols rows
```

## Key Insight

Transpose is only an index mapping.

For every original position:

```python
row, col
```

copy the value into:

```python
col, row
```

So the core operation is:

```python
answer[col][row] = matrix[row][col]
```

Once this mapping is clear, the implementation is straightforward.

## Algorithm

1. Let `rows` be the number of rows.
2. Let `cols` be the number of columns.
3. Create an answer matrix with `cols` rows and `rows` columns.
4. For every `row` from `0` to `rows - 1`:
   1. For every `col` from `0` to `cols - 1`:
      1. Set `answer[col][row] = matrix[row][col]`.
5. Return `answer`.

## Correctness

For every valid position `(row, col)` in the original matrix, the algorithm copies `matrix[row][col]` into `answer[col][row]`.

This is exactly the definition of matrix transpose.

The answer matrix has `cols` rows and `rows` columns, so every transposed position exists.

Every original element is copied once, and every output position corresponds to exactly one original position.

Therefore, the returned matrix is the transpose of the input matrix.

## Complexity

Let:

```python
m = number of rows
n = number of columns
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n)` | Every element is copied once |
| Space | `O(m * n)` | The output matrix stores every element |

Auxiliary space outside the output is `O(1)`.

## Implementation

```python
class Solution:
    def transpose(self, matrix: list[list[int]]) -> list[list[int]]:
        rows = len(matrix)
        cols = len(matrix[0])

        answer = [[0] * rows for _ in range(cols)]

        for row in range(rows):
            for col in range(cols):
                answer[col][row] = matrix[row][col]

        return answer
```

## Code Explanation

We first read the dimensions:

```python
rows = len(matrix)
cols = len(matrix[0])
```

Then we create the output matrix with swapped dimensions:

```python
answer = [[0] * rows for _ in range(cols)]
```

If the input is `2 x 3`, then the answer is `3 x 2`.

Next, we visit every cell:

```python
for row in range(rows):
    for col in range(cols):
```

and copy it into its transposed position:

```python
answer[col][row] = matrix[row][col]
```

Finally:

```python
return answer
```

returns the completed transposed matrix.

## Testing

```python
def test_transpose():
    s = Solution()

    assert s.transpose([
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
    ]) == [
        [1, 4, 7],
        [2, 5, 8],
        [3, 6, 9],
    ]

    assert s.transpose([
        [1, 2, 3],
        [4, 5, 6],
    ]) == [
        [1, 4],
        [2, 5],
        [3, 6],
    ]

    assert s.transpose([
        [1],
        [2],
        [3],
    ]) == [
        [1, 2, 3],
    ]

    assert s.transpose([
        [1, 2, 3],
    ]) == [
        [1],
        [2],
        [3],
    ]

    print("all tests passed")

test_transpose()
```

Test meaning:

| Test | Why |
|---|---|
| Square matrix | Checks normal diagonal flip |
| Rectangular `2 x 3` matrix | Checks shape changes to `3 x 2` |
| Single column | Becomes one row |
| Single row | Becomes one column |