Given a matrix with N rows and M columns, return the transpose of the matrix.
The transpose is formed by converting rows into columns and columns into rows. An element present at mat[row][col] moves to transpose[col][row].
Example 1
Input: mat = [[1, 2, 3], [4, 5, 6]]
Output: [[1, 4], [2, 5], [3, 6]]
Explanation: The first row becomes the first column, the second row becomes the second column, and the third column becomes the third row.
Example 2
Input: mat = [[10, -2], [3, 4], [5, 6]]
Output: [[10, 3, 5], [-2, 4, 6]]
Explanation: A 3 x 2 matrix becomes a 2 x 3 matrix after transposition.
Approach
The transpose of a matrix is formed by swapping the row and column indices of every element. We traverse the original matrix once and place each element at its transposed position in a new matrix.
Algorithm
Create a transpose matrix with the number of rows and columns interchanged.
Traverse every row using an outer loop.
For each row, traverse all columns using an inner loop.
Place the current element at
transpose[col][row].Return the transpose matrix after all elements have been processed.
Dry Run
tranpose of a matrix
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to return the transpose of a matrix. vector<vector<int>> transposeMatrix(vector<vector<int>>& mat) { // Store total number of rows. int n = mat.size(); // Handle an empty matrix. if (n == 0) { return {}; } // Store total number of columns. int m = mat[0].size(); // Create a transpose matrix with swapped dimensions. vector<vector<int>> transposed(m, vector<int>(n, 0)); // Traverse every row from top to bottom. for (int row = 0; row < n; row++) { // Traverse every column from left to right. for (int col = 0; col < m; col++) { // Place the current value at swapped indices. transposed[col][row] = mat[row][col]; } } // Return the final transpose matrix. return transposed; }};// Driver code.int main() { vector<vector<int>> mat = {{1, 2, 3}, {4, 5, 6}}; Solution sol; vector<vector<int>> ans = sol.transposeMatrix(mat); for (int row = 0; row < (int)ans.size(); row++) { for (int col = 0; col < (int)ans[row].size(); col++) { if (col > 0) { cout << " "; } cout << ans[row][col]; } cout << "\n"; } return 0;}Complexity Analysis
Time Complexity: O(N × M), traversal visits every matrix cell exactly once.
Space Complexity: O(N × M), transpose matrix stores all values from the original matrix.
Interview follow-up Questions
A matrix with dimension N x M becomes a matrix with dimension M x N.
Be the first to add a comment.