Transpose Matrix

Difficulty: Easy | Acceptance: 76.30% | Paid: No Topics: Array, Matrix, Simulation

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.

• Table of Contents
• Examples
• Constraints
• New Matrix Construction

Examples

Example 1:

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

Example 2:

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

Constraints

- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 1000
- 1 <= m * n <= 10^5
- -10^9 <= matrix[i][j] <= 10^9

New Matrix Construction

Intuition The transpose of an M x N matrix is an N x M matrix where the element at position (i, j) in the original matrix moves to position (j, i) in the new matrix. Since the dimensions change (unless the matrix is square), we must allocate a new matrix to store the result.

Steps

• Determine the dimensions of the original matrix: m rows and n columns.
• Initialize a new result matrix with dimensions n x m.
• Iterate through the original matrix using two nested loops.
• For each element at (i, j), assign it to result[j][i].
• Return the result matrix.

from typing import List

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        m = len(matrix)
        n = len(matrix[0])
        # Initialize an n x m matrix filled with zeros
        res = [[0] * m for _ in range(n)]
        
        for i in range(m):
            for j in range(n):
                res[j][i] = matrix[i][j]
                
        return res

Complexity

• Time: O(M * N) — We visit every element in the matrix exactly once.
• Space: O(M * N) — We create a new matrix to store the result.
• Notes: This is the most straightforward approach and handles all matrix dimensions correctly.