Transpose Matrix

Q: What is the time complexity of transposing a matrix?

It is O(m × n) , because each of the m × n values is copied once and nothing less can produce the answer. The new matrix takes O(m × n) space, which is the size of the output itself.

Q: Can you transpose a matrix in place?

For a square matrix, yes: swap matrix[i][j] with matrix[j][i] for every cell above the diagonal, using O(1) extra memory. For a non-square matrix the result has a different shape, so with a list of rows you need a new matrix.

Q: How do you transpose a non-square matrix?

Create a result with n rows of length m , where the input has m rows of length n . Then copy every value with result[j][i] = matrix[i][j] . The diagonal idea of the square case does not apply, because the two matrices do not share a shape.

BeginnerArrays and strings

+10

You get a matrix of integers as a list of rows: matrix[i][j] is the value in row i, column j. Return its transpose, the matrix you get by turning every row into a column. The value at row i, column j moves to row j, column i. The matrix does not have to be square: an m × n matrix becomes an n × m one.

Function

transpose(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: the m × n matrix, as a list of m rows of n integers
Returnsinteger-2d-array: the n × m transpose, as a list of n rows of m integers

Constraints

1 ≤ m, n ≤ 1000, where m = matrix.length and n = matrix[i].length
m × n ≤ 5000
Every row has the same length n.
-1000 ≤ matrix[i][j] ≤ 1000

Examples

Input: matrix = [[1, 2, 3], [4, 5, 6]]
Output: [[1, 4], [2, 5], [3, 6]]
Explanation: The first row [1, 2, 3] becomes the first column and [4, 5, 6] the second. Reading the result row by row gives [1, 4], [2, 5], [3, 6]: the 2 × 3 matrix turned into a 3 × 2 one.

+15 hidden tests on Submit

Follow-up

Suppose the matrix is stored as one flat array of m × n values, row after row. Can you transpose a non-square matrix inside that array, with no second array?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Transposing is a pure change of address: the value at (i, j) moves to (j, i), and nothing is computed. The work is to get the shape right. A non-square matrix stored as a list of rows cannot be transposed in place, because the answer has n rows of length m instead of m rows of length n, so you build a new matrix of the swapped size and fill it.

Read the matrix one column at a time

Intuition

Row j of the answer is column j of the input, read from top to bottom. So build the answer one row at a time: for each column j from 0 to n-1, collect matrix[0][j], matrix[1][j], and so on down to matrix[m-1][j], and append that list as the next row.

For [[1, 2, 3], [4, 5, 6]], column 0 reads 1 then 4, column 1 reads 2 then 5, column 2 reads 3 then 6. The answer is [[1, 4], [2, 5], [3, 6]], with n = 3 rows of m = 2 values.

Every value is read once and written once, so the time is O(m × n) and the result takes O(m × n) space. The cost is in the access pattern: building one new row touches every input row, jumping from row to row instead of reading along one.

Algorithm

Let m be the number of rows and n the length of a row.
For each column j from 0 to n-1, start an empty list.
Append matrix[i][j] to it for every i from 0 to m-1.
Append the list to the result as row j, and return the result after the last column.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    result = []
    for j in range(n):
        # Column j, read top to bottom, becomes row j of the answer.
        column = []
        for i in range(m):
            column.append(matrix[i][j])
        result.append(column)
    return result

Fill a new n × m grid by mirroring each cell

Intuition

Decide the shape first, then fill it. The answer has n rows of length m, so create that grid up front. Then read the input in its natural order, row by row and left to right, and drop each value at its mirrored address: result[j][i] = matrix[i][j].

The rule is correct because transposing is exactly that swap of the two indexes. In the square example [[1, 2], [3, 4]], the 1 and 4 on the diagonal land where they were, 2 goes from (0, 1) to (1, 0), and 3 from (1, 0) to (0, 1), giving [[1, 3], [2, 4]].

Each of the m × n values is copied once, so the time is O(m × n), and the new grid is the O(m × n) space the output needs anyway. Reading the input along its rows visits memory in the order it is stored, and each result row is made once at its final size.

Algorithm

Let m be the number of rows and n the length of a row.
Create result with n rows, each holding m values.
For every row i and every column j of the input, set result[j][i] = matrix[i][j].
Return result.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    # The answer has n rows of m values each.
    result = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            result[j][i] = matrix[i][j]
    return result

Pitfalls and edge cases

Almost every wrong answer comes from the shape, not from the values.

Building the result with the original shape. A result of m rows and n columns only works for square input; for the 2 × 3 example, writing result[2][0] runs off the end. The result needs n rows of length m.
Swapping in place on a non-square matrix. Swapping matrix[i][j] with matrix[j][i] only works when m = n, and even then the loop must cover only the cells above the diagonal (j > i), or every pair is swapped twice and the matrix comes back unchanged.
Sharing one row object. In Python, [[0] * m] * n makes n references to the same list, so writing one cell writes the whole column. Build each row separately.
Forgetting the column sizes in C. The caller reads *returnSize as the number of result rows, n, and (*returnColumnSizes)[j] as the length of each row, m.

Frequently asked questions4

What is the transpose of a matrix?

It is the matrix you get by swapping rows and columns: the value at row i, column j moves to row j, column i. A 2 × 3 matrix becomes 3 × 2, and transposing twice gives the original back.

What is the time complexity of transposing a matrix?

It is O(m × n), because each of the m × n values is copied once and nothing less can produce the answer. The new matrix takes O(m × n) space, which is the size of the output itself.

Can you transpose a matrix in place?

For a square matrix, yes: swap matrix[i][j] with matrix[j][i] for every cell above the diagonal, using O(1) extra memory. For a non-square matrix the result has a different shape, so with a list of rows you need a new matrix.

How do you transpose a non-square matrix?

Create a result with n rows of length m, where the input has m rows of length n. Then copy every value with result[j][i] = matrix[i][j]. The diagonal idea of the square case does not apply, because the two matrices do not share a shape.

Python

def transpose(matrix):
    # Write code here

Test cases

Case 1

Case 2

Input

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

Expected

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