Transpose Matrix
EasyPrompt
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] <= 109
Approaches
1 approach with complexity analysis and trade-offs.
The most straightforward and optimal approach is to directly construct the transposed matrix based on its definition. The transpose of a matrix is formed by turning all the rows of a given matrix into columns and vice-versa. This means the element at row i and column j in the original matrix moves to row j and column i in the new matrix. This approach creates a new matrix with swapped dimensions and fills it by iterating through the original matrix.
Algorithm
- Get the dimensions of the input
matrix:Rrows andCcolumns. - Create a new result matrix,
transposedMatrix, with dimensionsCrows andRcolumns. - Iterate through the original
matrixusing nested loops. The outer loop iterates through rowsrfrom0toR-1, and the inner loop iterates through columnscfrom0toC-1. - In each iteration, copy the element
matrix[r][c]totransposedMatrix[c][r]. - After the loops complete, return the
transposedMatrix.
Walkthrough
This method involves creating a new matrix with dimensions n x m, where the original matrix has dimensions m x n. We then iterate through each element of the original matrix and place it in its new position in the transposed matrix.
Here's the step-by-step algorithm:
- Determine the dimensions of the input
matrix. Let's say it hasRrows andCcolumns. - Create a new result matrix,
transposedMatrix, with dimensionsC x R. - Iterate through the original
matrixwith two nested loops. The outer loop runs fromr = 0toR-1(for rows), and the inner loop runs fromc = 0toC-1(for columns). - For each element
matrix[r][c], assign it to the corresponding position in the new matrix:transposedMatrix[c][r] = matrix[r][c]. - After the loops complete, the
transposedMatrixwill hold the transposed version of the inputmatrix. ReturntransposedMatrix.
For example, if matrix[0][1] is 2, it will be placed at result[1][0].
class Solution { public int[][] transpose(int[][] matrix) { int R = matrix.length; if (R == 0) { return new int[0][0]; } int C = matrix[0].length; int[][] transposedMatrix = new int[C][R]; for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { transposedMatrix[c][r] = matrix[r][c]; } } return transposedMatrix; }}Complexity
Time
O(R * C), where `R` is the number of rows and `C` is the number of columns. We need to iterate through each of the `R * C` elements of the matrix once to perform the transposition.
Space
O(R * C), where `R` is the number of rows and `C` is the number of columns. We create a new matrix of size `C x R` to store the result. The space required is proportional to the number of elements in the matrix.
Trade-offs
Pros
Simple to understand and implement.
Works for any
m x nmatrix, including square and non-square matrices.Optimal in terms of time complexity, as every element must be visited.
Cons
Requires extra space proportional to the size of the matrix. This is unavoidable for non-square matrices where the dimensions change.
Solutions
Solution
class Solution {public int[][] transpose(int[][] matrix) { int m = matrix.length, n = matrix[0].length; int[][] ans = new int[n][m]; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { ans[i][j] = matrix[j][i]; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.