Transpose Matrix

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

O(m × n) : each of the m × n values is copied once, and nothing less can produce the answer. The new matrix takes O(m × n) space, 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, with O(1) extra memory. A non-square matrix changes shape, so with a list of rows you need a new matrix.

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 value at row i, column j moves to row j, column i, so every row becomes a column. 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 row [1, 2, 3] becomes the first column and [4, 5, 6] the second. Read row by row, the result is [1, 4], [2, 5], [3, 6]: a 3 × 2 matrix.

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 computes nothing: the value at (i, j) moves to (j, i). The work is the shape. The answer has n rows of length m, so a non-square list of rows cannot be transposed in place; 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 top to bottom. For [[1, 2, 3], [4, 5, 6]], column 0 reads 1 then 4, so the first row of the answer is [1, 4].

Every value is read once and written once: O(m × n) time, and O(m × n) space for the result. Building each new row jumps across every input row instead of reading along one, which is the slower way to walk memory.

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

Create the n × m result up front, then read the input in the order it is stored, row by row, and drop each value at its mirrored address: result[j][i] = matrix[i][j]. That is correct because a transpose is exactly this swap of indexes, applied once to every cell.

Each value is copied once, so the time is O(m × n), and the grid is the O(m × n) space the output needs anyway. Reading along rows visits memory in stored order, and each result row is allocated 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

Building the result with the input's shape. For the 2 × 3 example, writing result[2][0] runs off the end: the result needs n rows of length m.
Swapping matrix[i][j] with matrix[j][i] in place. That only works when m = n, and only over cells with j > i; a loop over every cell swaps each pair twice and returns the matrix unchanged.
In Python, [[0] * m] * n makes n references to one list, so writing one cell writes a whole column. Build each row separately.
In C, the caller reads *returnSize as the number of result rows, n, and (*returnColumnSizes)[j] as each row's length, m.

Frequently asked questions3

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?

O(m × n): each of the m × n values is copied once, and nothing less can produce the answer. The new matrix takes O(m × n) space, 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, with O(1) extra memory. A non-square matrix changes shape, so with a list of rows you need a new matrix.

def transpose(matrix):
    # Write code here

Test #1

Test #2

Argument

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

Expected Output

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