Transpose Matrix - Video Solutions

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.