867 - Transpose Matrix

Difficulty: Easy | Pattern: Matrix Manipulation | Company tags: Amazon, Apple, Google

Problem Statement

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.

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]]

Note: Unlike LeetCode 48 (Rotate Image), the output matrix may have different dimensions (non-square input).

Solution

def transpose(matrix: list[list[int]]) -> list[list[int]]:
    rows, cols = len(matrix), len(matrix[0])
    # Result is cols x rows
    result = [[0] * rows for _ in range(cols)]
    
    for r in range(rows):
        for c in range(cols):
            result[c][r] = matrix[r][c]
    
    return result

One-Liner with zip

def transpose(matrix: list[list[int]]) -> list[list[int]]:
    return [list(row) for row in zip(*matrix)]

zip(*matrix) unpacks the matrix rows as arguments to zip, which pairs up all elements at index 0, then index 1, etc. — effectively transposing.

Algorithm Flow

Dry Run

matrix = [[1,2,3],[4,5,6]] (2×3 → result is 3×2)

Original:    Transpose:
1 2 3        1 4
4 5 6        2 5
             3 6

• result[0][0] = matrix[0][0] = 1
• result[0][1] = matrix[1][0] = 4
• result[1][0] = matrix[0][1] = 2
• result[2][2] = matrix[2][1] doesn't exist for 2×3 input, only goes to result[2][1] = matrix[1][2] = 6

Comparison: Transpose vs Rotate

Operation	Input	Output
Transpose	m×n	n×m (flip on diagonal)
90° clockwise rotate	n×n	n×n (transpose + reverse rows)

Transpose is a building block for rotation — but note transpose alone does NOT rotate.

Edge Cases

• Square matrix → symmetric result dimensions
• 1×n matrix → n×1 result
• 1×1 matrix → same 1×1

Complexity

• Time: O(m × n) — visit every element once
• Space: O(m × n) — output matrix (cannot do in-place for non-square matrices)

Key Terms

Term	Definition
Transpose	Reflecting a matrix over its main diagonal, so element (r, c) becomes (c, r).
Main diagonal	The line from the top-left to bottom-right corner; the axis of reflection for a transpose.
Row-major traversal	Iterating a matrix row by row, column by column — the natural order for building the transpose.
Non-square matrix	A matrix where rows != cols; the transpose swaps the dimensions (m×n becomes n×m).
zip(*matrix) unpacking	A Python idiom that unpacks rows as separate arguments to zip, grouping elements by column index.

FAQ

Q: Can this be solved in-place? A: Only for square matrices, by swapping matrix[i][j] with matrix[j][i] for i < j. For non-square matrices the output has different dimensions, so a new array is required.

Q: What if the input matrix is empty or has empty rows? A: Return an empty list immediately — there's nothing to transpose, and len(matrix[0]) would throw if not guarded.

Q: Why doesn't transpose alone rotate a matrix? A: Transpose only reflects over the main diagonal. A 90° rotation requires transpose followed by reversing each row (clockwise) or reversing each column first (counter-clockwise).

Q: What's the follow-up interviewers usually ask? A: "Can you do it in-place for a square matrix without extra space?" — this leads into LeetCode 48 (Rotate Image), which requires an in-place layer-by-layer swap.

Q: How does the zip(*matrix) trick work under the hood? A: *matrix unpacks each row as a positional argument to zip, which then pairs up the i-th element of every row into a tuple — effectively producing the columns of the original matrix, i.e., the transposed rows.

Quick Revision

• Transpose flips a matrix over its main diagonal: result[c][r] = matrix[r][c].
• Output dimensions swap: an m×n input produces an n×m output.
• Cannot transpose non-square matrices in-place — must allocate a new result array.
• Square matrices can be transposed in-place via swapping (i,j) and (j,i) for i < j.
• Time complexity is O(m×n); every element is visited exactly once.
• Space complexity is O(m×n) for the new result matrix (O(1) extra if in-place on a square matrix).
• zip(*matrix) is a concise Pythonic one-liner that achieves the same result.
• Transpose is a reusable building block for 90° matrix rotation (transpose + reverse rows/columns).

Related Problems

• 48 - Rotate Image — uses transpose as a building block for in-place 90° rotation.
• 54 - Spiral Matrix — another classic matrix-traversal pattern (not present in this directory).
• 73 - Set Matrix Zeroes — related matrix-manipulation pattern using in-place marking (not present in this directory).