Untitled

 avatar
unknown
plain_text
a month ago
1.9 kB
2
Indexable
import java.util.HashMap;

public class LargestZeroSumSubmatrix {
    public static int largestZeroSumSubmatrix(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        int maxArea = 0;

        // Fix the left column boundary
        for (int c1 = 0; c1 < m; c1++) {
            int[] rowSum = new int[n]; // Row-wise collapsed sum

            // Expand the right column boundary
            for (int c2 = c1; c2 < m; c2++) {
                // Compute the sum for each row within column boundaries c1 to c2
                for (int row = 0; row < n; row++) {
                    rowSum[row] += matrix[row][c2];
                }

                // Find the max height (rows) for sum 0
                int height = largestSubarrayWithSumZero(rowSum);
                int width = c2 - c1 + 1;
                maxArea = Math.max(maxArea, width * height);
            }
        }
        return maxArea;
    }

    // Function to find the longest subarray with sum 0
    private static int largestSubarrayWithSumZero(int[] arr) {
        HashMap<Integer, Integer> prefixMap = new HashMap<>();
        int prefixSum = 0, maxLen = 0;

        for (int i = 0; i < arr.length; i++) {
            prefixSum += arr[i];

            if (prefixSum == 0) {
                maxLen = i + 1;
            }

            if (prefixMap.containsKey(prefixSum)) {
                maxLen = Math.max(maxLen, i - prefixMap.get(prefixSum));
            } else {
                prefixMap.put(prefixSum, i);
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, -3, 4},
            {-3, -1, 2, 1},
            {2, 3, -4, -2}
        };

        System.out.println("Largest Zero Sum Submatrix Area: " + largestZeroSumSubmatrix(matrix));
    }
}
Editor is loading...
Leave a Comment