Transpose Matrix

Tags

Transpose Matrix

Category

Arrays

Difficulty

Easy

Problem Statement

Given a 2D matrix of integers, return its transpose. The transpose of a matrix is obtained by flipping it over its main diagonal, turning rows into columns and columns into rows. If the input matrix has dimensions m x n, the output should be n x m.

Intuition

The element at position (i, j) in the original matrix goes to position (j, i) in the transposed matrix. We iterate through every element, placing it in its transposed position in a new matrix.

Approach

  1. Determine the number of rows (m) and columns (n) of the input matrix.
  2. Create a new matrix of dimensions n x m.
  3. For each row i and column j in the input:
    • Set result[j][i] = matrix[i][j].
  4. Return the result matrix.

Pseudocode

function transposeMatrix(matrix):
    rows = length(matrix)
    cols = length(matrix[0])
    result = new matrix of size cols x rows
    for i from 0 to rows - 1:
        for j from 0 to cols - 1:
            result[j][i] = matrix[i][j]
    return result

Time & Space Complexity

  • Time: O(m * n) — Every element is visited exactly once.
  • Space: O(m * n) — For the output matrix.

Key Insights

  • The transpose swaps rows and columns: the i-th row becomes the i-th column.
  • For square matrices (m == n), transposition can be done in-place by swapping matrix[i][j] with matrix[j][i] for i < j.
  • For non-square matrices, an in-place transpose is not straightforward, so a new matrix is typically allocated.
  • Transposing twice returns the original matrix.

Edge Cases

  • Single-element matrix (1x1) — the transpose is the same matrix.
  • Single-row matrix (1 x n) — becomes an n x 1 column matrix.
  • Single-column matrix (m x 1) — becomes a 1 x m row matrix.
  • Square matrix — dimensions remain the same after transposition.

Linked mentions