Jagged Array Transpose

Problem Statement

Write a Java program that implements a method to transpose a jagged array (a 2D array where each row can have a different length), converting rows to columns to create a new jagged array. The i-th row of the transposed array contains all elements from the i-th column of the original array, with row lengths varying based on the number of non-null elements in each column. The program should return the transposed array and test the implementation with irregular jagged arrays, including edge cases like empty arrays, arrays with empty rows, and arrays with varying row lengths. You can visualize this as flipping a ragged grid so that each column becomes a row, like reorganizing a collection of uneven lists into a new set of lists based on column positions.

Input: A jagged 2D array of integers, where each row may have a different length (e.g., matrix = {{1, 2, 3}, {4}, {5, 6}}). Output: A new jagged array where the i-th row contains elements from the i-th column of the input (e.g., {{1, 4, 5}, {2, 6}, {3}}). Constraints:

• The number of rows is between 0 and 100.
• Each row’s length is between 0 and 100.
• Elements are integers between -10^4 and 10^4.
• The matrix may be empty or contain empty or null rows. Example:
• Input: matrix = {{1, 2, 3}, {4}, {5, 6}}
• Output: {{1, 4, 5}, {2, 6}, {3}}
• Explanation: Column 0 ([1, 4, 5]) becomes row 0, column 1 ([2, 6]) becomes row 1, column 2 ([3]) becomes row 2.
• Input: matrix = {{1, 2}, {}, {3}}
• Output: {{1, 3}, {2}}
• Explanation: Column 0 ([1, 3]) becomes row 0, column 1 ([2]) becomes row 1.

Pseudocode

FUNCTION transposeJaggedArray(matrix)
    IF matrix is null OR matrix is empty THEN
        RETURN empty array
    ENDIF
    SET maxCols to maximum row length in matrix
    CREATE result as empty dynamic array
    FOR j from 0 to maxCols - 1
        CREATE tempList as empty list
        FOR i from 0 to number of rows in matrix - 1
            IF matrix[i] is not null AND j < length of matrix[i] THEN
                ADD matrix[i][j] to tempList
            ENDIF
        ENDFOR
        IF tempList is not empty THEN
            CREATE newRow array of size tempList size
            COPY tempList elements to newRow
            ADD newRow to result
        ENDIF
    ENDFOR
    RETURN result
ENDFUNCTION

FUNCTION main()
    SET testMatrices to jagged 2D arrays
    FOR each matrix in testMatrices
        PRINT original matrix
        CALL transposeJaggedArray(matrix)
        PRINT transposed matrix
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Check if the input matrix is null or empty. If so, return an empty array.
2. Determine the maximum number of columns (maxCols) by finding the longest row.
3. Initialize an empty ArrayList<int[]> for the result.
4. For each column index j from 0 to maxCols-1: a. Create a temporary list to collect elements from column j. b. Iterate through each row i:
   • If row i is not null and j is within its length, add matrix[i][j] to the temporary list. c. If the temporary list is not empty, convert it to an array and add it as a row to the result.
5. Return the result as a jagged array.
6. In the main method, create test matrices with irregular row lengths and call transposeJaggedArray to verify correctness, printing the original and transposed matrices.

Java Implementation

import java.util.ArrayList;

public class JaggedArrayTranspose {
    // Transposes a jagged array, converting rows to columns
    public int[][] transposeJaggedArray(int[][] matrix) {
        // Check for null or empty matrix
        if (matrix == null || matrix.length == 0) {
            return new int[0][];
        }
        // Find maximum number of columns
        int maxCols = 0;
        for (int[] row : matrix) {
            if (row != null && row.length > maxCols) {
                maxCols = row.length;
            }
        }
        // Create result array
        ArrayList<int[]> result = new ArrayList<>();
        // Process each column
        for (int j = 0; j < maxCols; j++) {
            ArrayList<Integer> tempList = new ArrayList<>();
            // Collect elements from column j
            for (int i = 0; i < matrix.length; i++) {
                if (matrix[i] != null && j < matrix[i].length) {
                    tempList.add(matrix[i][j]);
                }
            }
            // Convert non-empty tempList to array and add to result
            if (!tempList.isEmpty()) {
                int[] newRow = new int[tempList.size()];
                for (int k = 0; k < tempList.size(); k++) {
                    newRow[k] = tempList.get(k);
                }
                result.add(newRow);
            }
        }
        // Convert ArrayList to int[][]
        return result.toArray(new int[0][]);
    }

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

        // Test case 1: Jagged array with varying row lengths
        int[][] matrix1 = {{1, 2, 3}, {4}, {5, 6}};
        System.out.println("Test case 1:");
        System.out.println("Original matrix:");
        printMatrix(matrix1);
        System.out.println("Transposed matrix:");
        printMatrix(transposer.transposeJaggedArray(matrix1));

        // Test case 2: Jagged array with empty rows
        int[][] matrix2 = {{1, 2}, {}, {3}};
        System.out.println("\nTest case 2:");
        System.out.println("Original matrix:");
        printMatrix(matrix2);
        System.out.println("Transposed matrix:");
        printMatrix(transposer.transposeJaggedArray(matrix2));

        // Test case 3: Empty matrix
        int[][] matrix3 = {};
        System.out.println("\nTest case 3:");
        System.out.println("Original matrix:");
        printMatrix(matrix3);
        System.out.println("Transposed matrix:");
        printMatrix(transposer.transposeJaggedArray(matrix3));

        // Test case 4: Matrix with negative numbers
        int[][] matrix4 = {{-1, -2, -3}, {-4, -5}, {-6}};
        System.out.println("\nTest case 4:");
        System.out.println("Original matrix:");
        printMatrix(matrix4);
        System.out.println("Transposed matrix:");
        printMatrix(transposer.transposeJaggedArray(matrix4));

        // Test case 5: Null matrix
        int[][] matrix5 = null;
        System.out.println("\nTest case 5:");
        System.out.println("Original matrix:");
        printMatrix(matrix5);
        System.out.println("Transposed matrix:");
        printMatrix(transposer.transposeJaggedArray(matrix5));
    }

    // Helper method to print jagged matrix
    private static void printMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            System.out.println("[]");
            return;
        }
        System.out.println("[");
        for (int i = 0; i < matrix.length; i++) {
            System.out.print("  [");
            if (matrix[i] == null || matrix[i].length == 0) {
                System.out.print("]");
            } else {
                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.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, 5]
  [2, 6]
  [3]
]

Test case 2:
Original matrix:
[
  [1, 2]
  []
  [3]
]
Transposed matrix:
[
  [1, 3]
  [2]
]

Test case 3:
Original matrix:
[]
Transposed matrix:
[]

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

Test case 5:
Original matrix:
[]
Transposed matrix:
[]

Explanation:

• Test case 1: Transposes {{1, 2, 3}, {4}, {5, 6}} to {{1, 4, 5}, {2, 6}, {3}}, where column 0 ([1, 4, 5]) becomes row 0, etc.
• Test case 2: Transposes {{1, 2}, {}, {3}} to {{1, 3}, {2}}, handling empty rows.
• Test case 3: Empty matrix returns empty matrix.
• Test case 4: Transposes {{-1, -2, -3}, {-4, -5}, {-6}} to {{-1, -4, -6}, {-2, -5}, {-3}}, handling negatives.
• Test case 5: Null matrix returns empty matrix.

How It Works

• Step 1: Check if the matrix is null or empty. For {{1, 2, 3}, {4}, {5, 6}}, proceed.
• Step 2: Find maxCols = 3 (longest row).
• Step 3: Initialize result as an empty ArrayList<int[]>.
• Step 4: For each column j:
  • j = 0: Collect [1, 4, 5] (from matrix[0][0], matrix[1][0], matrix[2][0]) → add to result.
  • j = 1: Collect [2, 6] (from matrix[0][1], matrix[2][1]; matrix[1] has no column 1) → add to result.
  • j = 2: Collect [3] (from matrix[0][2]; others have no column 2) → add to result.
• Example Trace: For test case 1, builds [[1, 4, 5], [2, 6], [3]] by collecting column elements.
• Main Method: Tests with irregular jagged arrays, including empty rows, empty matrix, negatives, and null matrix.
• Transpose Property: Each column becomes a row, with row lengths varying based on non-null column elements.

Complexity Analysis Table

Note:

• m is the number of rows, c is the maximum row length (maxCols).
• Time complexity: O(m * c), as each element is visited once to build the transposed rows.
• Space complexity: O(m * c), for the result array storing up to m * c elements.
• Best, average, and worst cases are O(m * c).

✅ Tip: Use a dynamic structure like ArrayList to handle varying row lengths in the transposed array. Test with irregular arrays, including empty and null rows, to ensure robustness.

⚠ Warning: Check for null rows and varying row lengths to avoid NullPointerException or ArrayIndexOutOfBoundsException. Ensure the result array only includes non-empty rows.