Transpose Matrix

Problem Statement

Write a Java program that implements a method to transpose a 2D array (matrix), swapping its rows and columns to create a new matrix where the element at position [i][j] in the original matrix becomes the element at position [j][i] in the result. The program should return the transposed matrix as a new 2D array and test the implementation with square and non-square matrices, including edge cases like single-row or single-column matrices. You can visualize this as flipping a grid of numbers over its main diagonal, turning rows into columns and columns into rows, like rearranging a chessboard so that the row of pieces becomes a column.

Input: A 2D array (matrix) of integers with dimensions m × n (e.g., matrix = [[1, 2, 3], [4, 5, 6]]). Output: A new 2D array of dimensions n × m representing the transposed matrix (e.g., [[1, 4], [2, 5], [3, 6]]). Constraints:

• 1 ≤ m, n ≤ 100 (where m is the number of rows and n is the number of columns).
• Elements are integers between -10^9 and 10^9.
• The matrix is guaranteed to be non-empty and rectangular (all rows have the same number of columns). Example:
• Input: matrix = [[1, 2, 3], [4, 5, 6]]
• Output: [[1, 4], [2, 5], [3, 6]]
• Explanation: The 2×3 matrix is transposed to a 3×2 matrix, with row 1 ([1, 2, 3]) becoming column 1 ([1, 4]), etc.
• Input: matrix = [[1, 2], [3, 4]]
• Output: [[1, 3], [2, 4]]
• Explanation: The 2×2 square matrix is transposed, swapping elements across the main diagonal.

Pseudocode

FUNCTION transposeMatrix(matrix)
    IF matrix is null OR matrix is empty THEN
        RETURN null
    ENDIF
    SET rows to number of rows in matrix
    SET cols to number of columns in matrix
    CREATE result matrix of size cols × rows
    FOR i from 0 to rows - 1
        FOR j from 0 to cols - 1
            SET result[j][i] to matrix[i][j]
        ENDFOR
    ENDFOR
    RETURN result
ENDFUNCTION

FUNCTION main()
    SET testMatrices to arrays of 2D arrays
    FOR each matrix in testMatrices
        CALL transposeMatrix(matrix)
        PRINT result
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Check if the input matrix is null or empty. If so, return null.
2. Determine the dimensions of the input matrix: rows (m) and columns (n).
3. Create a new result matrix of size n × m (columns × rows).
4. Iterate through each element matrix[i][j] in the input matrix: a. Set result[j][i] to matrix[i][j], effectively swapping rows and columns.
5. Return the result matrix.
6. In the main method, create test matrices (square and non-square) with various sizes and call transposeMatrix to verify correctness.

Java Implementation

public class TransposeMatrix {
    // Transposes a matrix by swapping rows and columns
    public int[][] transposeMatrix(int[][] matrix) {
        // Check for null or empty matrix
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return null;
        }
        // Get dimensions
        int rows = matrix.length;
        int cols = matrix[0].length;
        // Create result matrix with swapped dimensions
        int[][] result = new int[cols][rows];
        // Transpose by copying elements
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                result[j][i] = matrix[i][j];
            }
        }
        return result;
    }

    // Main method to test transposeMatrix with various inputs
    public static void main(String[] args) {
        TransposeMatrix transposer = new TransposeMatrix();

        // Test case 1: 2x3 non-square matrix
        int[][] matrix1 = {{1, 2, 3}, {4, 5, 6}};
        System.out.println("Test case 1:");
        System.out.println("Original matrix:");
        printMatrix(matrix1);
        int[][] result1 = transposer.transposeMatrix(matrix1);
        System.out.println("Transposed matrix:");
        printMatrix(result1);

        // Test case 2: 2x2 square matrix
        int[][] matrix2 = {{1, 2}, {3, 4}};
        System.out.println("Test case 2:");
        System.out.println("Original matrix:");
        printMatrix(matrix2);
        int[][] result2 = transposer.transposeMatrix(matrix2);
        System.out.println("Transposed matrix:");
        printMatrix(result2);

        // Test case 3: 1x3 single-row matrix
        int[][] matrix3 = {{1, 2, 3}};
        System.out.println("Test case 3:");
        System.out.println("Original matrix:");
        printMatrix(matrix3);
        int[][] result3 = transposer.transposeMatrix(matrix3);
        System.out.println("Transposed matrix:");
        printMatrix(result3);

        // Test case 4: 3x1 single-column matrix
        int[][] matrix4 = {{1}, {2}, {3}};
        System.out.println("Test case 4:");
        System.out.println("Original matrix:");
        printMatrix(matrix4);
        int[][] result4 = transposer.transposeMatrix(matrix4);
        System.out.println("Transposed matrix:");
        printMatrix(result4);

        // Test case 5: Empty matrix
        int[][] matrix5 = {};
        System.out.println("Test case 5:");
        System.out.println("Original matrix:");
        printMatrix(matrix5);
        int[][] result5 = transposer.transposeMatrix(matrix5);
        System.out.println("Transposed matrix:");
        printMatrix(result5);
    }

    // Helper method to print matrix
    private static void printMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            System.out.println("null");
            return;
        }
        System.out.println("[");
        for (int i = 0; i < matrix.length; i++) {
            System.out.print("  [");
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j]);
                if (j < matrix[i].length - 1) {
                    System.out.print(", ");
                }
            }
            System.out.println("]");
        }
        System.out.println("]");
    }
}

Output

Running the main method produces:

Test case 1:
Original matrix:
[
  [1, 2, 3]
  [4, 5, 6]
]
Transposed matrix:
[
  [1, 4]
  [2, 5]
  [3, 6]
]
Test case 2:
Original matrix:
[
  [1, 2]
  [3, 4]
]
Transposed matrix:
[
  [1, 3]
  [2, 4]
]
Test case 3:
Original matrix:
[
  [1, 2, 3]
]
Transposed matrix:
[
  [1]
  [2]
  [3]
]
Test case 4:
Original matrix:
[
  [1]
  [2]
  [3]
]
Transposed matrix:
[
  [1, 2, 3]
]
Test case 5:
Original matrix:
null
Transposed matrix:
null

Explanation:

• Test case 1: Transposes a 2×3 matrix to a 3×2 matrix.
• Test case 2: Transposes a 2×2 square matrix, swapping elements across the diagonal.
• Test case 3: Transposes a 1×3 matrix to a 3×1 matrix.
• Test case 4: Transposes a 3×1 matrix to a 1×3 matrix.
• Test case 5: Returns null for an empty matrix.

How It Works

• Step 1: The transposeMatrix method checks if the matrix is null or empty. For [[1, 2, 3], [4, 5, 6]], it proceeds.
• Step 2: Get dimensions: rows = 2, cols = 3.
• Step 3: Create a result matrix of size 3×2.
• Step 4: Iterate through the input matrix:
  • matrix[0][0] = 1 → result[0][0] = 1
  • matrix[0][1] = 2 → result[1][0] = 2
  • matrix[0][2] = 3 → result[2][0] = 3
  • matrix[1][0] = 4 → result[0][1] = 4
  • matrix[1][1] = 5 → result[1][1] = 5
  • matrix[1][2] = 6 → result[2][1] = 6
• Example Trace: For [[1, 2, 3], [4, 5, 6]], builds [[1, 4], [2, 5], [3, 6]] by swapping indices.
• Main Method: Tests with square (2×2), non-square (2×3, 1×3, 3×1), and empty matrices, printing inputs and results.
• Transpose Property: Creates a new matrix with swapped dimensions, where each matrix[i][j] maps to result[j][i].

Complexity Analysis Table

Note:

• m is the number of rows, n is the number of columns in the input matrix.
• Time complexity: O(m*n), as the algorithm iterates through each element of the m×n matrix once.
• Space complexity: O(m*n), for the result matrix. Temporary variables use O(1) space.
• Best, average, and worst cases are O(m*n).

✅ Tip: Ensure the result matrix has dimensions n×m for an m×n input matrix. Test with both square and non-square matrices to verify correctness, especially single-row or single-column cases.

⚠ Warning: Ensure the input matrix is not null and is rectangular (all rows have the same number of columns) to avoid NullPointerException or ArrayIndexOutOfBoundsException.