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] <= 109Problem Overview: You are given an m x n matrix. The task is to return its transpose, meaning rows become columns and columns become rows. Element matrix[i][j] moves to position result[j][i].
Approach 1: Direct New Matrix Construction (Time: O(m * n), Space: O(m * n))
The most straightforward solution allocates a new matrix with dimensions n x m. Iterate through every element of the original matrix using two nested loops. For each cell (i, j), assign its value to result[j][i]. This works for both square and rectangular matrices and is typically what interviewers expect for general cases involving matrix transformations.
The key insight is that transposition simply swaps row and column indices. You scan the entire matrix once and write each element to its transposed position. The algorithm relies only on iteration and index manipulation, which makes it easy to implement across languages.
This approach fits most production and interview scenarios because the problem statement returns a new matrix anyway. The runtime is O(m * n) since every cell is visited once, and the extra space is also O(m * n) for the result matrix.
Approach 2: In-place Transposition for Square Matrices (Time: O(n^2), Space: O(1))
If the matrix is square (n x n), you can transpose it in-place by swapping elements across the main diagonal. Iterate through the upper triangle of the matrix and swap matrix[i][j] with matrix[j][i]. This avoids allocating another matrix.
The diagonal acts as the symmetry line. Elements above the diagonal swap with their mirrored positions below it. By restricting swaps to j > i, each pair is processed exactly once. This technique is common in array and simulation style matrix problems.
The time complexity is O(n^2) because every element in the upper triangle is processed. Space complexity is O(1) since swaps happen directly in the original matrix. This approach only works for square matrices; rectangular matrices require a new structure.
Recommended for interviews: Use the direct new matrix construction approach. It handles any m x n matrix and clearly demonstrates understanding of index mapping. Mention the in-place diagonal swap optimization if the interviewer asks about square matrices or space optimization.
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.
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.
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.
Time Complexity: O(n^2)
Space Complexity: O(1)
Let m be the number of rows and n be the number of columns in the matrix matrix. According to the definition of transpose, the transposed matrix ans will have n rows and m columns.
For any position (i, j) in ans, it corresponds to the position (j, i) in the matrix matrix. Therefore, we traverse each element in the matrix matrix and transpose it to the corresponding position in ans.
After the traversal, we return ans.
The time complexity is O(m times n), where m and n are the number of rows and columns in the matrix matrix, respectively. Ignoring the space consumption of the answer, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
| 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) |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct New Matrix Construction | O(m * n) | O(m * n) | General case for any rectangular matrix where a new transposed matrix is returned |
| In-place Transposition (Square Matrix) | O(n^2) | O(1) | When the matrix is square and minimizing extra memory is important |
LeetCode Transpose Matrix Solution Explained - Java • Nick White • 29,081 views views
Watch 9 more video solutions →Practice Transpose Matrix with our built-in code editor and test cases.
Practice on FleetCode