How do you approach Transpose Matrix?

If the input is m x n, what are the dimensions of the output?

What is the time complexity of Transpose Matrix?

Time complexity: O(m n) - every cell copied once. Space complexity: O(m n) for the output.

What are common mistakes on Transpose Matrix?

Transposing row and column in the index. It reads fine and fails on any non-square input. Overwriting cells a later iteration still needs to read - most in-place matrix problems want a marker pass first. Bounds checks that cover only some of the four edges.

gitGood.dev

← Back to problems

Transpose Matrix

EasyAlgorithms

Description

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: cell `(i, j)` of the input becomes cell `(j, i)` of the output. Note that the matrix may be **rectangular** (rows and columns counts can differ), so you generally cannot transpose it in place.

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]]

Explanation: A 2x3 matrix becomes a 3x2 matrix.

Example 3

Input: matrix = [[1]]

Output: [[1]]

Constraints

- m == matrix.length - n == matrix[i].length - 1 <= m, n <= 100 - -10^4 <= matrix[i][j] <= 10^4

Transpose Matrix: approach, complexity and pitfalls

An easy matrix problem, graded against 7 test cases (4 of them hidden).

The pattern: Matrix

2D grid traversal, rotation, and in-place manipulation.

Reach for it when you see: A grid input, spiral or diagonal traversal, or an in-place transformation constraint.

More Matrixproblems →

If you are stuck

Show the 3-step hint ladder

If the input is m x n, what are the dimensions of the output?
Allocate an n x m result, then copy each element to its mirrored position.
result[j][i] = matrix[i][j] for every i, j - a double loop is all you need.

The optimal approach

Show the approach: Direct Index Swap into a New Matrix

Allocate an `n x m` output and set `result[j][i] = matrix[i][j]` for every cell. Because the shape changes for rectangular inputs, building a new matrix is the natural approach (in-place swapping only works for square matrices).

Time: O(m * n) - every cell copied once
Space: O(m * n) for the output

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Matrix mistakes

These apply to the pattern as a whole, not just this problem.

Transposing row and column in the index. It reads fine and fails on any non-square input.
Overwriting cells a later iteration still needs to read - most in-place matrix problems want a marker pass first.
Bounds checks that cover only some of the four edges.