Transpose Matrix
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.
Examples :
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]
Explanation: Each row becomes a column and column has become a row.
Input: matrix = [[1,2,3],[4,5,6]]
Output: [[1,4],[2,5],[3,6]]
Explanation: In this case, the number of rows and columns are swapped, resulting in a matrix with 3 rows and 2 columns. Each element's row and column indices are switched.
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
1 <= m * n <= 10^5
-10^9 <= matrix[i][j] <= 10^9
Approach
In 11th-12th grade, you might have learned about transposing a matrix. When transposing a matrix, we convert all the rows into columns and all the columns into rows. We need to do the same thing here.
So how will we be doing this in programming?
When a matrix is transposed, its dimensions change. The number of columns in the original matrix becomes the number of rows in the transposed matrix, and the number of rows in the original matrix becomes the number of columns in the transposed matrix. If the original matrix has m rows and n columns, the transposed matrix will have n rows and m columns. To achieve this, we need to create a new matrix answer of size n x m.
To perform the transposition, we take each row of the original matrix and assign its elements as a column in the new matrix.
When transposing a matrix, our goal is to rearrange the elements in such a way that the matrix is flipped along its main diagonal.
The main diagonal is the line running from the top-left corner to the bottom-right corner of a square or rectangular matrix. To do this, we need to make every row in the original matrix correspond to a column in the transposed matrix, and vice versa.
For a matrix A, the element at position A[i][j] becomes B[j][i] in the transposed matrix B.
If the matrix is square (having equal numbers of rows and columns, m=n), its dimensions remain unchanged after transposition.
However, for non-square matrices (m≠n), the dimensions swap, resulting in a matrix with n rows and m columns.
For example, a 2×3 matrix would become a 3×2 matrix upon transposition. This process applies to all matrices, regardless of whether they are square or rectangular.
Why Do We Swap Indices (i, j) to (j, i)?
The main diagonal consists of elements where the row and column indices are the same, i.e., (i, i) (e.g., the elements at (0,0), (1,1), etc.).
To transpose, we flip the matrix along this diagonal so that:
- Elements in the rows of the original matrix shift to the columns of the transposed matrix.
- Elements in the columns of the original matrix shift to the rows of the transposed matrix.
Mathematically, this flipping is achieved by swapping the indices (i, j) to (j, i) for every element.
When transposing a matrix, our goal is to rearrange the elements in such a way that the matrix is flipped along its main diagonal.
To do this, we need to make every row in the original matrix correspond to a column in the transposed matrix, and vice versa. Let’s dive into why and how this works step by step:
Why This Works for Any Matrix
If the original matrix has m rows and n columns, the transposed matrix will have n rows and m columns. This is because each row in the original matrix becomes a column in the transposed matrix. By swapping the positions (i, j) to (j, i), we make sure the elements stay in the same order relative to the diagonal, but their orientation changes. Rows turn into columns, and columns turn into rows. The overall arrangement of the data stays the same, just reorganized to match the transposed structure.
For example, if the original matrix is:
How to Code it up
Step 1: Get Matrix Dimensions
- Determine the number of rows (m) and columns (n) in the input matrix.
Step 2: Create an Empty Transposed Matrix
- Initialize a 2D matrix of size n×m with default values (e.g., zeros or placeholders). This will store the transposed result.
Step 3: Iterate Through the Input Matrix
- Use two nested loops:
- The outer loop iterates through each row (i) of the input matrix.
- The inner loop iterates through each column (j) of the input matrix.
Step 4: Assign Elements to the Transposed Matrix
- In each iteration, copy the element at position (i,j) in the input matrix to position (j,i) in the transposed matrix.
Step 5: Return the Transposed Matrix
- Once all elements have been copied, return the transposed matrix as the result.
Code for All Languages
C++
class Solution {
public:
vector<vector<int>> transpose(vector<vector<int>>& matrix) {
// Get the number of rows (m) and columns (n) in the original matrix
int m = matrix.size(); // Number of rows
int n = matrix[0].size(); // Number of columns
// Create a new matrix of size n x m to store the transposed result
vector<vector<int>> transposedMatrix(n, vector<int>(m));
// Traverse through each element of the original matrix
for (int i = 0; i < m; i++) { // Loop through rows
for (int j = 0; j < n; j++) { // Loop through columns
// Assign the element at (i, j) in the original matrix to (j, i) in the transposed matrix
transposedMatrix[j][i] = matrix[i][j];
}
}
// Return the transposed matrix
return transposedMatrix;
}
};
Java
class Solution {
public int[][] transpose(int[][] matrix) {
// Get the number of rows (m) and columns (n) in the original matrix
int m = matrix.length;
int n = matrix[0].length;
// Create a new matrix of size n x m to store the transposed result
int[][] transposedMatrix = new int[n][m];
// Traverse through each element of the original matrix
for (int i = 0; i < m; i++) { // Loop through rows
for (int j = 0; j < n; j++) { // Loop through columns
// Assign the element at (i, j) in the original matrix to (j, i) in the new matrix
transposedMatrix[j][i] = matrix[i][j];
}
}
// Return the transposed matrix
return transposedMatrix;
}
}
Python
class Solution(object):
def transpose(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
# Get the number of rows (m) and columns (n) in the original matrix
m = len(matrix)
n = len(matrix[0])
# Create a new matrix of size n x m to store the transposed result
transposed_matrix = [[0] * m for _ in range(n)]
# Traverse through each element of the original matrix
for i in range(m): # Loop through rows
for j in range(n): # Loop through columns
# Assign the element at (i, j) in the original matrix to (j, i) in the new matrix
transposed_matrix[j][i] = matrix[i][j]
# Return the transposed matrix
return transposed_matrix
Javascript
/**
* @param {number[][]} matrix
* @return {number[][]}
*/
var transpose = function(matrix) {
// Get the number of rows (m) and columns (n) in the original matrix
const m = matrix.length; // Number of rows
const n = matrix[0].length; // Number of columns
// Create a new matrix of size n x m to store the transposed result
const transposedMatrix = Array.from({ length: n }, () => Array(m).fill(0));
// Traverse through each element of the original matrix
for (let i = 0; i < m; i++) { // Loop through rows
for (let j = 0; j < n; j++) { // Loop through columns
// Assign the element at (i, j) in the original matrix to (j, i) in the new matrix
transposedMatrix[j][i] = matrix[i][j];
}
}
// Return the transposed matrix
return transposedMatrix;
};
Time Complexity: O(m×n)
- Matrix Initialization: A new matrix of size n×m is created to store the transposed result. Initializing this matrix involves allocating memory and assigning default values for n×m elements.
Time complexity: O(m×n) - Transposing Elements: To compute the transpose, every element in the m×n input matrix is accessed once and placed into its corresponding position in the n×m transposed matrix. This involves two nested loops: The total number of iterations is m×n, with each iteration performing a constant-time operation.
Time complexity: O(m×n) - The outer loop iterates over all rows (m).
- The inner loop iterates over all columns (n).
- Returning the Result: Returning the transposed matrix involves passing its reference. This step is performed in constant time.
Time complexity: O(1).
Total Time Complexity
The initialization and the element-by-element transposition dominate the overall time complexity.
Adding these steps, the total complexity becomes: O(m×n)+O(m×n)=O(m×n)
Space Complexity: O(n×m)
- Input Matrix: The input matrix is provided as an argument to the function, and no modifications are made. This contributes O(m×n) to the overall memory, but since the function itself does not allocate this memory, it is not included in the function's space complexity.
- Transposed Matrix: A new matrix of size n×m is created to store the result of the transpose operation. This requires memory allocation for n×m elements.
Space complexity: O(n×m) - Auxiliary Variables: The function uses a few integer variables to store indices (i, j), as well as m and n, which are required for matrix dimensions. These are constant in size.
Space complexity: O(1)
Total Space Complexity: The dominant term is the memory allocated for the transposed matrix.
Therefore, the overall space complexity is: O(n×m)
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.
You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.
The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.