Transpose Matrix
Allocate a swapped-dimension grid and copy with indices flipped.
2 min read
matrix
Problem#
Return the transpose of a given m x n matrix — the matrix whose row i is the original’s column i.
Examples#
[[1,2,3],[4,5,6],[7,8,9]]→[[1,4,7],[2,5,8],[3,6,9]][[1,2,3],[4,5,6]]→[[1,4],[2,5],[3,6]]
Constraints#
m == matrix.length,n == matrix[i].length,1 <= m, n <= 1000.
Approach#
Allocate an n x m result. Copy matrix[i][j] to result[j][i].
Solution#
class Solution {public: vector<vector<int>> transpose(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); vector<vector<int>> ans(n, vector<int>(m)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) ans[j][i] = matrix[i][j]; return ans; }};func transpose(matrix [][]int) [][]int { m, n := len(matrix), len(matrix[0]) ans := make([][]int, n) for i := range ans { ans[i] = make([]int, m) } for i := 0; i < m; i++ { for j := 0; j < n; j++ { ans[j][i] = matrix[i][j] } } return ans}from typing import List
class Solution: def transpose(self, matrix: List[List[int]]) -> List[List[int]]: m, n = len(matrix), len(matrix[0]) ans = [[0] * m for _ in range(n)] for i in range(m): for j in range(n): ans[j][i] = matrix[i][j] return ansvar transpose = function(matrix) { const m = matrix.length, n = matrix[0].length; const ans = Array.from({ length: n }, () => new Array(m)); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { ans[j][i] = matrix[i][j]; } } return ans;};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 < m; i++) { for (int j = 0; j < n; j++) { ans[j][i] = matrix[i][j]; } } return ans; }}function transpose(matrix: number[][]): number[][] { const m: number = matrix.length, n: number = matrix[0].length; const ans: number[][] = Array.from({ length: n }, () => new Array(m)); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { ans[j][i] = matrix[i][j]; } } return ans;}Editorial#
For non-square matrices, in-place transposition is impossible without a complex cycle-following algorithm — so an extra O(m*n) buffer is appropriate. For square matrices, swap above-diagonal entries with their mirror.
Complexity#
- Time: O(m*n).
- Space: O(m*n).
Concept revision#
Related#