Teaching Kids Programming – Algorithm to Transpose a Matrix

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a matrix A, return the transpose of A. The transpose of a matrix is the matrix flipped over it’s main diagonal, switching the row and column indices of the matrix.

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

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

Note:
1 <= A.length <= 1000
1 <= A[0].length <= 1000

Transpose a Matrix

Transpose a Matrix means swap columns and rows. First allocate a new matrix with dimensions swapped (e.g. column number is the row number and row number is the column number of original matrix). Then, iterate the original matrix, to assign M[r][c] to T[c][r] where M is the original matrix and T is the target matrix.

The time and space complexity are both O(RC) where R and C are the dimesions (number of rows, and number of columns) for the original matrix.

1
2
3
4
5
6
7
8

class Solution:
    def transpose(self, A: List[List[int]]) -> List[List[int]]:
        R, C = len(A), len(A[0])
        T = [[None] * R for _ in range(C)]
        for r in range(R):
            for c in range(C):
                T[c][r] = A[r][c]
        return T

class Solution:
    def transpose(self, A: List[List[int]]) -> List[List[int]]:
        R, C = len(A), len(A[0])
        T = [[None] * R for _ in range(C)]
        for r in range(R):
            for c in range(C):
                T[c][r] = A[r][c]
        return T

Pythonic way to Transpose a Matrix

In Python, we can do something Pythonic using the zip function and the star operator:

1
2
3

return list(zip(*A))
# or 
return [v for v in zip(*A)]

return list(zip(*A))
# or 
return [v for v in zip(*A)]

–EOF (The Ultimate Computing & Technology Blog) —