Transpose Matrix

XXX. Matrix Transpose

Array

Matrix

In-Place

Problem Statement:

Write a function to transpose a matrix. The transpose of a matrix is obtained by flipping it along its diagonal. That is, the element at position (i, j) in the original matrix is placed at position (j, i) in the transposed matrix.

Examples:

Input: [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: [[1, 4, 7], [2, 5, 8], [3, 6, 9]]

Approach 1: New Transposed Matrix

1. Initialize a new matrix with dimensions m x n (rows become columns and vice versa).
2. Iterate over each element in the input matrix.
3. For each element at (i, j), place it in position (j, i) in the new matrix.
4. Return the new transposed matrix.

Approach 2: In-Place Transpose (Square Matrix)

1. This approach works only for square matrices where the number of rows equals the number of columns.
2. Iterate through the matrix using nested loops.
3. For each pair (i, j) where j > i, swap the elements matrix[i][j] and matrix[j][i].
4. This avoids redundant swaps and ensures that the transpose is done in-place without extra memory.

Algorithm Intuition:

The key idea is to rearrange the elements in the matrix such that rows become columns and columns become rows:

• In the **new transposed matrix** approach, we allocate space for a new matrix and directly place each element in its transposed position.
• In the **in-place transpose**, we take advantage of the square matrix property, swapping elements across the diagonal to avoid extra memory usage.

Complexity:

New Transposed Matrix:
Time Complexity: O(n × m), where n is the number of rows and m is the number of columns.
Space Complexity: O(n × m), for the new matrix.

In-Place Transpose:
Time Complexity: O(n²), where n is the number of rows (or columns in a square matrix).
Space Complexity: O(1), since no additional memory is used.

Java Implementation:

// New Transposed Matrix
public int[][] transpose(int[][] matrix) {
    int n = matrix.length, m = matrix[0].length;
    int[][] transposedMatrix = new int[m][n];

    // Swap rows and columns
    for (int i = 0; i < m; i++) 
        for (int j = 0; j < n; j++) 
            transposedMatrix[i][j] = matrix[j][i];

    return transposedMatrix;
}

// In-Place Transpose (Square Matrix)
public int[][] transposeInPlace(int[][] matrix) {
    int n = matrix.length;

    // Swap elements across the diagonal
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }

    return matrix;
}