Transpose Matrix

How it works

For square matrices, we can transpose in-place by swapping elements across the main diagonal. We only need to process elements above (or below) the diagonal to avoid swapping twice.

However, for non-square matrices, in-place transposition is not possible since the dimensions change. In this case, we fall back to creating a new matrix. This approach optimizes memory usage when the input is square.

Steps

1. Check if the matrix is square (ROWS == COLS).
2. If square, iterate through elements above the diagonal where c < r.
3. Swap each element matrix[r][c] with matrix[c][r].
4. Return the modified matrix.
5. If not square, create a new res matrix with swapped dimensions.
6. Copy elements from (r, c) to (c, r) and return the res matrix.

Complexity

• Time complexity: O(n * m)
• Space complexity: O(n * m)

Where n is the number of rows and m is the number of columns in the matrix.

Things to watch for

Swapping Dimensions Incorrectly

When creating the result matrix, you must swap the dimensions. The original matrix has dimensions ROWS x COLS, but the transposed matrix must have dimensions COLS x ROWS. A common mistake is creating a matrix with the same dimensions as the original, which leads to index out of bounds errors or incorrect results.

Confusing Transpose with In-Place Swap for Non-Square Matrices

For square matrices, you can transpose in-place by swapping elements across the diagonal. However, for non-square matrices, in-place transposition is not possible because the dimensions change. Attempting to apply the in-place swap technique to a rectangular matrix will result in incorrect output or runtime errors.

from typing import List

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        ROWS, COLS = len(matrix), len(matrix[0])

        if ROWS == COLS:
            for r in range(ROWS):
                for c in range(r):
                    matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]

            return matrix

        res = [[0] * ROWS for _ in range(COLS)]

        for r in range(ROWS):
            for c in range(COLS):
                res[c][r] = matrix[r][c]

        return res

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& matrix) {
        int ROWS = matrix.size(), COLS = matrix[0].size();

        if (ROWS == COLS) {
            for (int r = 0; r < ROWS; r++) {
                for (int c = 0; c < r; c++) {
                    swap(matrix[r][c], matrix[c][r]);
                }
            }

            return matrix;
        }

        vector<vector<int>> res(COLS, vector<int>(ROWS));

        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                res[c][r] = matrix[r][c];
            }
        }

        return res;
    }
};