Transpose Matrix

Allocate a swapped-dimension grid and copy with indices flipped.

Easy
Time O(m*n) Space O(m*n)
LeetCode
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#

Transpose Matrix
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.