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.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[1,4,7],[2,5,8],[3,6,9]]
Example 2:
Input: matrix = [[1,2,3],[4,5,6]] Output: [[1,4],[2,5],[3,6]]
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10001 <= m * n <= 105-109 <= matrix[i][j] <= 109The key idea in Transpose Matrix is to swap the rows and columns of the matrix. If the original matrix has m rows and n columns, the transposed matrix will have n rows and m columns. Each element at position (i, j) in the original matrix should be placed at (j, i) in the result.
A common approach is to create a new matrix with dimensions n x m. Then iterate through every element of the original matrix and place it in the corresponding transposed position. This simulation-based method is simple and avoids modifying the input matrix directly.
During iteration, assign values using the rule result[j][i] = matrix[i][j]. Since every element is visited exactly once, the solution scales linearly with the number of cells. This makes the approach efficient and easy to implement for interview scenarios involving arrays and matrix manipulation.
The overall time complexity is O(m × n), and the extra space used is also O(m × n) for the resulting matrix.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Create new matrix and map (i,j) → (j,i) | O(m × n) | O(m × n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
We don't need any special algorithms to do this. You just need to know what the transpose of a matrix looks like. Rows become columns and vice versa!
To transpose the given matrix, we create a new matrix with dimensions transposed: the number of rows of the new matrix is equal to the number of columns in the original matrix, and vice versa. We fill in the new matrix by iterating through each element of the original matrix and placing it at the transposed position in the new matrix.
Time Complexity: O(m * n) where m and n are the number of rows and columns respectively.
Space Complexity: O(m * n) since a new matrix is created.
1def transpose(matrix):
2 rows = len(matrix)
3 cols = len(matrix[0])
4 return [[matrix[i]This is a simple implementation using list comprehensions to create the transposed matrix by swapping rows with columns in a concise manner.
This approach specifically applies to square matrices where m = n. For such matrices, we can swap elements using an in-place technique, avoiding additional space usage. For each element above the main diagonal, swap it with its corresponding element below the diagonal.
Time Complexity: O(n^2)
Space Complexity: O(1)
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
In-place transposition is possible when the matrix is square (n × n). In that case, elements across the diagonal can be swapped without extra memory. For non-square matrices, a new matrix is typically required.
Yes, matrix manipulation problems like transpose are common in coding interviews at top tech companies. They test understanding of indexing, loops, and 2D array handling. While the problem itself is easy, it often appears as part of larger matrix-based questions.
The optimal approach is to iterate through the matrix and place each element at position (i, j) into (j, i) in a new matrix. This directly constructs the transpose in one pass. It runs in O(m × n) time and is simple to implement.
A 2D array (or matrix) is the most suitable structure for this problem. You create another 2D array with swapped dimensions to store the transposed result. This allows constant-time access and assignment for each element.
This C solution swaps each pair matrix[i][j] and matrix[j][i] for i != j, directly altering the input matrix only for square matrices.