Skip to main content
Talentd

Transpose Matrix - Solution & Explanation

EasyArrayMatrixSimulation14 min readAsked at: Amazon, Microsoft, Apple +4
Practice this problem

Problem Statement

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.length
  • n == matrix[i].length
  • 1 <= m, n <= 1000
  • 1 <= 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.

This solution uses dynamic memory allocation to create a transposed matrix. For each element matrix[i][j] in the original matrix, transposed[j][i] is assigned the same value.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n) where m and n are the number of rows and columns respectively.
Space Complexity: O(m * n) since a new matrix is created.

Try this approach in the editor →

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.

This C solution swaps each pair matrix[i][j] and matrix[j][i] for i != j, directly altering the input matrix only for square matrices.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Direct New Matrix Construction

Time Complexity: O(m * n) where m and n are the number of rows and columns respectively.
Space Complexity: O(m * n) since a new matrix is created.

In-place Transposition for Square Matrices

Time Complexity: O(n^2)
Space Complexity: O(1)

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct New Matrix ConstructionO(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

Video Solution

LeetCode Transpose Matrix Solution Explained - Java • Nick White • 29,240 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Transpose Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays