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] <= 109To 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.
This solution uses dynamic memory allocation to create a transposed matrix. For each element matrix[i][j] in the original matrix, transposed[j][i] is assigned the same value.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Direct New Matrix Construction | Time Complexity: O(m * n) where m and n are the number of rows and columns respectively. |
| In-place Transposition for Square Matrices | Time Complexity: O(n^2) |
Rotate Image - Matrix - Leetcode 48 • NeetCode • 268,928 views views
Watch 9 more video solutions →Practice Transpose Matrix with our built-in code editor and test cases.
Practice on FleetCode