Sparse Matrix Sum

Problem Statement

Write a Java program that represents a sparse matrix using a jagged array (a 2D array where each row can have a different length) and computes the sum of all non-zero elements. The program should return the sum as a long integer and test the implementation with matrices of varying row lengths, including edge cases like empty matrices, matrices with empty rows, and matrices with all zeros. You can visualize this as calculating the total value of non-zero items in a grid where each row may have a different number of columns, like summing the values of scattered resources in an uneven terrain map.

Input: A jagged 2D array of integers, where each row may have a different length (e.g., matrix = {{1, 0, 2}, {3}, {0, 4, 5, 0}}). Output: A long integer representing the sum of all non-zero elements (e.g., 15 for the example above). 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 rows. Example:
• Input: matrix = {{1, 0, 2}, {3}, {0, 4, 5, 0}}
• Output: 15
• Explanation: Non-zero elements are 1, 2, 3, 4, 5; sum = 1 + 2 + 3 + 4 + 5 = 15.
• Input: matrix = {{0, 0}, {0}, {}}
• Output: 0
• Explanation: No non-zero elements, so sum = 0.

Pseudocode

FUNCTION sumSparseMatrix(matrix)
    IF matrix is null OR matrix is empty THEN
        RETURN 0
    ENDIF
    SET sum to 0
    FOR each row in matrix
        IF row is not null THEN
            FOR each element in row
                IF element is not zero THEN
                    SET sum to sum + element
                ENDIF
            ENDFOR
        ENDIF
    ENDFOR
    RETURN sum
ENDFUNCTION

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

Algorithm Steps

1. Check if the input matrix is null or empty. If so, return 0.
2. Initialize a variable sum to 0.
3. Iterate through each row of the matrix: a. Check if the row is not null. b. Iterate through each element in the row. c. If the element is non-zero, add it to sum.
4. Return the final sum.
5. In the main method, create test matrices with varying row lengths and call sumSparseMatrix to verify correctness.

Java Implementation

public class SparseMatrixSum {
    // Computes the sum of non-zero elements in a jagged 2D array
    public long sumSparseMatrix(int[][] matrix) {
        // Check for null or empty matrix
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        // Initialize sum
        long sum = 0;
        // Iterate through each row
        for (int[] row : matrix) {
            // Check for non-null row
            if (row != null) {
                // Iterate through each element in the row
                for (int element : row) {
                    // Add non-zero elements to sum
                    if (element != 0) {
                        sum += element;
                    }
                }
            }
        }
        return sum;
    }

    // Main method to test sumSparseMatrix with various inputs
    public static void main(String[] args) {
        SparseMatrixSum summer = new SparseMatrixSum();

        // Test case 1: Jagged matrix with non-zero elements
        int[][] matrix1 = {{1, 0, 2}, {3}, {0, 4, 5, 0}};
        System.out.println("Test case 1:");
        System.out.println("Matrix:");
        printMatrix(matrix1);
        System.out.println("Sum of non-zero elements: " + summer.sumSparseMatrix(matrix1));

        // Test case 2: Matrix with all zeros
        int[][] matrix2 = {{0, 0}, {0}, {0, 0}};
        System.out.println("Test case 2:");
        System.out.println("Matrix:");
        printMatrix(matrix2);
        System.out.println("Sum of non-zero elements: " + summer.sumSparseMatrix(matrix2));

        // Test case 3: Matrix with empty rows
        int[][] matrix3 = {{}, {1, 2}, {}};
        System.out.println("Test case 3:");
        System.out.println("Matrix:");
        printMatrix(matrix3);
        System.out.println("Sum of non-zero elements: " + summer.sumSparseMatrix(matrix3));

        // Test case 4: Single-row matrix
        int[][] matrix4 = {{1, 0, 3}};
        System.out.println("Test case 4:");
        System.out.println("Matrix:");
        printMatrix(matrix4);
        System.out.println("Sum of non-zero elements: " + summer.sumSparseMatrix(matrix4));

        // Test case 5: Matrix with negative numbers
        int[][] matrix5 = {{-1, 0}, {-2, -3, 0}, {4}};
        System.out.println("Test case 5:");
        System.out.println("Matrix:");
        printMatrix(matrix5);
        System.out.println("Sum of non-zero elements: " + summer.sumSparseMatrix(matrix5));

        // Test case 6: Null matrix
        int[][] matrix6 = null;
        System.out.println("Test case 6:");
        System.out.println("Matrix:");
        printMatrix(matrix6);
        System.out.println("Sum of non-zero elements: " + summer.sumSparseMatrix(matrix6));
    }

    // Helper method to print jagged 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("  [");
            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:
Matrix:
[
  [1, 0, 2]
  [3]
  [0, 4, 5, 0]
]
Sum of non-zero elements: 15
Test case 2:
Matrix:
[
  [0, 0]
  [0]
  [0, 0]
]
Sum of non-zero elements: 0
Test case 3:
Matrix:
[
  []
  [1, 2]
  []
]
Sum of non-zero elements: 3
Test case 4:
Matrix:
[
  [1, 0, 3]
]
Sum of non-zero elements: 4
Test case 5:
Matrix:
[
  [-1, 0]
  [-2, -3, 0]
  [4]
]
Sum of non-zero elements: -2
Test case 6:
Matrix:
null
Sum of non-zero elements: 0

Explanation:

• Test case 1: Sums non-zero elements 1, 2, 3, 4, 5 = 15.
• Test case 2: No non-zero elements, sum = 0.
• Test case 3: Sums non-zero elements 1, 2 = 3 (empty rows contribute 0).
• Test case 4: Sums non-zero elements 1, 3 = 4.
• Test case 5: Sums non-zero elements -1, -2, -3, 4 = -2.
• Test case 6: Returns 0 for a null matrix.

How It Works

• Step 1: The sumSparseMatrix method checks if the matrix is null or empty. For {{1, 0, 2}, {3}, {0, 4, 5, 0}}, it proceeds.
• Step 2: Initialize sum = 0.
• Step 3: Iterate through rows:
  • Row 0: [1, 0, 2] → sum = 0 + 1 + 0 + 2 = 3.
  • Row 1: [3] → sum = 3 + 3 = 6.
  • Row 2: [0, 4, 5, 0] → sum = 6 + 0 + 4 + 5 + 0 = 15.
• Example Trace: For test case 1, accumulates non-zero elements: 1 + 2 + 3 + 4 + 5 = 15.
• Main Method: Tests with jagged matrices of varying row lengths, including all zeros, empty rows, single-row, negative numbers, and null matrix, printing inputs and sums.
• Sparse Property: Only non-zero elements contribute to the sum, leveraging the jagged array’s flexibility for sparse matrices.

Complexity Analysis Table

Note:

• N is the total number of elements across all rows (sum of row lengths).
• Time complexity: O(N), as the algorithm visits each element once.
• Space complexity: O(1), as only a single sum variable is used (excluding input/output).
• Best, average, and worst cases are O(N).

✅ Tip: Use enhanced for loops for clean iteration over jagged arrays. Test with matrices containing empty rows, all zeros, and negative numbers to ensure robustness.

⚠ Warning: Check for null rows within the matrix to avoid NullPointerException. Use a long for the sum to handle large or negative numbers within the constraints.