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.

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.