Transpose Matrix solution and explanation
Google
9 more videos on this problem
LeetCode Transpose Matrix Solution Explained - JavaNick White · 3:32 · 29K views
Transpose Matrix - Leetcode 867 - PythonNeetCodeIO · 6:11 · 18K views
Leetcode | 867. Transpose Matrix | Easy | Java SolutionDeveloper Docs · 4:02 · 2K views
LeetCode 867 | Transpose Matrix | Solution Explained (Java)Xavier Elon · 5:57 · 1K views
Transpose Matrix | Leetcode 867 | Matrix | Live coding session 🔥🔥Coding Decoded · 6:55 · 706 views
867. Transpose Matrix (Leetcode Easy)Programming Live with Larry · 2:51 · 589 views
Leetcode 867 - Transpose Matrix with PythonThe Polyglot Programmer · 12:07 · 574 views
867. Transpose Matrix || LEETCODE SOLUTION || IN C++ || DATA STRUCTURE AND ALGORITHMAbhishweta Gupta · 1:35 · 497 views
Leetcode 867 - Transpose Matrix (JAVA Solution Explained!)LC Bear · 3:34 · 292 views
867. Transpose Matrix | Leetcode | PythonAbdullah Arshed · 5:03 · 235 views
The problem
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
Approach overview
Problem Overview: You are given an m x n matrix. The task is to return its transpose, meaning rows become columns and columns become rows. Element matrix[i][j] moves to position result[j][i].
Approach 1: Direct New Matrix Construction (Time: O(m * n), Space: O(m * n))
The most straightforward solution allocates a new matrix with dimensions n x m. Iterate through every element of the original matrix using two nested loops. For each cell (i, j), assign its value to result[j][i]. This works for both square and rectangular matrices and is typically what interviewers expect for general cases involving matrix transformations.
The key insight is that transposition simply swaps row and column indices. You scan the entire matrix once and write each element to its transposed position. The algorithm relies only on iteration and index manipulation, which makes it easy to implement across languages.
This approach fits most production and interview scenarios because the problem statement returns a new matrix anyway. The runtime is O(m * n) since every cell is visited once, and the extra space is also O(m * n) for the result matrix.
Approach 2: In-place Transposition for Square Matrices (Time: O(n^2), Space: O(1))
If the matrix is square (n x n), you can transpose it in-place by swapping elements across the main diagonal. Iterate through the upper triangle of the matrix and swap matrix[i][j] with matrix[j][i]. This avoids allocating another matrix.
The diagonal acts as the symmetry line. Elements above the diagonal swap with their mirrored positions below it. By restricting swaps to j > i, each pair is processed exactly once. This technique is common in array and simulation style matrix problems.
The time complexity is O(n^2) because every element in the upper triangle is processed. Space complexity is O(1) since swaps happen directly in the original matrix. This approach only works for square matrices; rectangular matrices require a new structure.
Recommended for interviews: Use the direct new matrix construction approach. It handles any m x n matrix and clearly demonstrates understanding of index mapping. Mention the in-place diagonal swap optimization if the interviewer asks about square matrices or space optimization.
Approach 1: Direct New Matrix Construction
To transpose the given matrix, we create a new matrix with dimensions transposed: the number of rows of the new matrix is equal to the number of columns in the original matrix, and vice versa. We fill in the new matrix by iterating through each element of the original matrix and placing it at the transposed position in the new matrix.
def transpose(matrix):
rows = len(matrix)
cols = len(matrix[0])
return [[matrix[i][j] for i in range(rows)] for j in range(cols)]class Solution {
public int[][] transpose(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
int[][] transposed = new int[cols][rows];
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
transposed[j][i] = matrix[i][j];
}
}
return transposed;
}
}#include <vector>
using namespace std;
vector<vector<int>> transpose(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
vector<vector<int>> transposed(cols, vector<int>(rows));
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
transposed[j][i] = matrix[i][j];
}
}
return transposed;
}function transpose(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
const transposed = Array.from({ length: cols }, () => Array(rows));
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
transposed[j][i] = matrix[i][j];
}
}
return transposed;
}#include <stdio.h>
#include <stdlib.h>
int** transpose(int** matrix, int matrixSize, int* matrixColSize, int* returnSize, int** returnColumnSizes){
int rows = matrixSize;
int cols = *matrixColSize;
int** transposed = (int**) malloc(cols * sizeof(int*));
*returnColumnSizes = (int*) malloc(rows * sizeof(int));
for(int i = 0; i < cols; i++){
transposed[i] = (int*) malloc(rows * sizeof(int));
(*returnColumnSizes)[i] = rows;
for(int j = 0; j < rows; j++){
transposed[i][j] = matrix[j][i];
}
}
*returnSize = cols;
return transposed;
}public class Solution {
public int[][] Transpose(int[][] matrix) {
int rows = matrix.Length;
int cols = matrix[0].Length;
int[][] transposed = new int[cols][];
for (int j = 0; j < cols; ++j) {
transposed[j] = new int[rows];
for (int i = 0; i < rows; ++i) {
transposed[j][i] = matrix[i][j];
}
}
return transposed;
}
}This is a simple implementation using list comprehensions to create the transposed matrix by swapping rows with columns in a concise manner.
Time Complexity: O(m * n)
Space Complexity: O(m * n)
Approach 2: In-place Transposition for Square Matrices
This approach specifically applies to square matrices where m = n. For such matrices, we can swap elements using an in-place technique, avoiding additional space usage. For each element above the main diagonal, swap it with its corresponding element below the diagonal.
def transpose_in_place(matrix):
n = len(matrix)
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]class Solution {
public void transposeInPlace(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
}#include <vector>
using namespace std;
void transposeInPlace(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
swap(matrix[i][j], matrix[j][i]);
}
}
}function transposeInPlace(matrix) {
const n = matrix.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
let temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}#include <stdio.h>
void transposeInPlace(int** matrix, int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}public class Solution {
public void TransposeInPlace(int[][] matrix) {
int n = matrix.Length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
}The Python solution uses tuple unpacking to swap elements across the main diagonal directly in the input matrix.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 3: Simulation
Let m be the number of rows and n be the number of columns in the matrix matrix. According to the definition of transpose, the transposed matrix ans will have n rows and m columns.
For any position (i, j) in ans, it corresponds to the position (j, i) in the matrix matrix. Therefore, we traverse each element in the matrix matrix and transpose it to the corresponding position in ans.
After the traversal, we return ans.
The time complexity is O(m times n), where m and n are the number of rows and columns in the matrix matrix, respectively. Ignoring the space consumption of the answer, the space complexity is O(1).
function transpose(matrix: number[][]): number[][] {
const [m, n] = [matrix.length, matrix[0].length];
const ans: number[][] = Array.from({ length: n }, () => Array(m).fill(0));
for (let i = 0; i < n; ++i) {
for (let j = 0; j < m; ++j) {
ans[i][j] = matrix[j][i];
}
}
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 j := range ans[i] {
ans[i][j] = matrix[j][i]
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Direct New Matrix Construction | Time Complexity: O(m * n) |
| In-place Transposition for Square Matrices | Time Complexity: O(n^2) |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct New Matrix Construction | O(m * n) | O(m * n) | General case for any rectangular matrix where a new transposed matrix is returned |
| In-place Transposition (Square Matrix) | O(n^2) | O(1) | When the matrix is square and minimizing extra memory is important |
Frequently asked questions
Is Transpose Matrix easy or hard?
Transpose Matrix is categorized as an Easy problem because it mainly tests basic matrix traversal and index manipulation. Once you understand that element (i, j) moves to (j, i), the implementation becomes straightforward.
Transpose Matrix Python/Java solution
In Python or Java, the solution typically uses two nested loops. Create a result matrix of size n x m and assign result[j][i] = matrix[i][j] while iterating through all elements. This implementation runs in O(m * n) time.
How to solve Transpose Matrix in O(n)?
For a general matrix, O(n) time is not possible because every element must be moved to its new position. The optimal solution is O(m * n), achieved by iterating through all cells and assigning matrix[i][j] to result[j][i].
What is the best approach for Transpose Matrix?
Directly constructing a new matrix and mapping each element from (i, j) to (j, i) is the best general approach. It works for any m x n matrix and runs in O(m * n) time with O(m * n) space. In-place swapping across the diagonal is an optimization only when the matrix is square.
Is Transpose Matrix asked at Google/Amazon/Meta?
Transpose-style matrix problems appear frequently in interviews at companies like Amazon, Google, and Meta. They are often used to test understanding of matrix traversal, index manipulation, and in-place transformations.
What data structure is used in Transpose Matrix?
The problem primarily uses a 2D array (matrix). The algorithm relies on nested iteration over rows and columns and simple index swapping or reassignment to construct the transposed matrix.
What is the time complexity of Transpose Matrix?
The standard solution scans every element once, giving O(m * n) time complexity for an m x n matrix. If the matrix is square and transposed in-place, the complexity becomes O(n^2), which is equivalent because the matrix contains n^2 elements.