Transpose Matrix
Understanding the Problem
We are given an m x n matrix and need to produce its transpose, an n x m matrix where the element at position (i, j) in the original ends up at position (j, i) in the result.
The first row of the original becomes the first column of the result, the second row becomes the second column, and so on. If the original matrix is 2x3 (2 rows, 3 columns), the transpose is 3x2 (3 rows, 2 columns).
The full operation reduces to one mapping: every element matrix[i][j] moves to result[j][i]. The work is in creating the output matrix with swapped dimensions and iterating without confusing the two index orders.
Key Constraints:
1 <= m * n <= 10^5→ At most 100,000 elements. A solution that visits each element once runs in O(m * n) and is efficient enough.-10^9 <= matrix[i][j] <= 10^9→ Values fit in a 32-bit signed integer. Since the transpose only copies values and never adds or multiplies them, overflow never arises and a 32-bitintis safe.
Approach 1: Direct Construction (Iterate Over Original)
Intuition
Allocate a result matrix with swapped dimensions and copy each element to its transposed position. If the original is m rows by n columns, the result is n rows by m columns. Walk through every cell (i, j) of the original and write its value to (j, i) in the result.
This is optimal. The transpose is a one-to-one mapping: every element of the original has exactly one destination, and every cell of the result is filled by exactly one source element, so reading each element once is both necessary and sufficient. That makes O(m n) time a lower bound. The output itself needs O(m n) space, and since the dimensions change for a non-square matrix, there is no in-place version that reuses the input.
Algorithm
- Get the number of rows
mand columnsnfrom the input matrix. - Create a new result matrix of dimensions n x m (rows and columns swapped).
- For each cell (i, j) in the original matrix, set
result[j][i] = matrix[i][j]. - Return the result matrix.
Example Walkthrough
Code
- Time Complexity: O(m * n). We visit every element of the matrix exactly once and do O(1) work per element.
- Space Complexity: O(m * n). We create a new n x m matrix to store the result. If we count only auxiliary space (excluding the output), it is O(1).
The next approach builds the same result with the same complexity but inverts the loop order. Instead of scanning the original and writing each element to its destination, it builds the result one row at a time by reading down a column of the original. This is the form behind the Python zip one-liner.
Approach 2: Column-Based Construction (Iterate Over Result)
Intuition
By definition, the j-th row of the transpose is the j-th column of the original. This approach builds the result directly from that statement: for each column index j, read straight down that column of the original (matrix[0][j], matrix[1][j], ..., matrix[m-1][j]) and use those values as row j of the result. The final mapping is identical to Approach 1, result[j][i] = matrix[i][j], only the loop order changes.
In Python this collapses to one line using zip: return [list(row) for row in zip(*matrix)]. The zip(*matrix) call unpacks the rows as separate arguments and zips them element by element, which groups the i-th element of every row together, that is, each column.
Algorithm
- Get the number of rows
mand columnsnfrom the input matrix. - For each column index
j(0 to n-1), create a new row by collectingmatrix[0][j], matrix[1][j], ..., matrix[m-1][j]. - Append each constructed row to the result.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(m n). We visit each of the m n elements exactly once. The iteration order does not change the total work.
- Space Complexity: O(m n). The result matrix stores all m n elements with swapped dimensions.