matrix · medium

Matrix Transpose

The transpose turns rows into columns: element (i, j) becomes (j, i), leaving the diagonal fixed. A square matrix transposes in place by swapping each pair across the diagonal — crucially iterating j from i+1 so each off-diagonal pair is swapped exactly once (starting at 0 double-swaps and cancels). It is O(n^2) time and O(1) space, but inherently memory-bound because one of the two accesses is always column-strided against row-major layout, so large transposes are cache-blocked.

The code

// In-place transpose of a SQUARE matrix: swap across the diagonal
for (int i = 0; i < n; ++i)
  for (int j = i + 1; j < n; ++j)   // upper triangle only (j > i)
    std::swap(a[i][j], a[j][i]);     // a[i][j] <-> a[j][i]

// Non-square (m x n -> n x m) needs a separate output buffer.

What this lesson walks through

1. 01Transpose — rows become columns
2. 02Swap a pair — A[0][2] ↔ A[2][0]
3. 03Upper triangle only — or you swap twice

Transpose reflects the matrix across its main diagonal (top-left to bottom-right): element A[i][j] moves to A[j][i]. Row 0 becomes column 0, row 1 becomes column 1. The diagonal itself (where i==j) never moves.