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:

matrix[row][col]

then in the transposed matrix it goes to:

answer[col][row]

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

Input and Output

Function shape:

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

Examples

Example 1:

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

The first row becomes the first column:

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

The result is:

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

Example 2:

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

This is a 2 x 3 matrix.

After transposition, it becomes a 3 x 2 matrix:

[
    [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:

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

then the answer should have:

cols rows

Key Insight

Transpose is only an index mapping.

For every original position:

row, col

copy the value into:

col, row

So the core operation is:

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:

m = number of rows
n = number of columns

Auxiliary space outside the output is O(1).

Implementation

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:

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

Then we create the output matrix with swapped dimensions:

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:

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

and copy it into its transposed position:

answer[col][row] = matrix[row][col]

Finally:

return answer

returns the completed transposed matrix.

Testing

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: