# Largest rectangular sub matrix whose sum is 0 in Java

Given a 2D matrix (also known as an array of arrays). The task is to find the largest rectangular sub-matrix (subarray) within it such that the sum of all elements in that sub-matrix is equal to 0.

1, -6, -7, 3

1, 8, 7, 9

7, -2, 0, 10

Output:  -6, -7

8, 7

-2, 0

Explanation: The sub-matrix with the sum closest to 0 is the entire input matrix itself.

Example 2

Input:     1, 2, 3

-3, -2, -1

1, 7, 5

Output: 1, 2, 3

-3, -2, -1

Explanation: The sub-matrix with the sum closest to 0 is the entire input matrix itself.

Example 3

Input: 5, 5, 5

-5, -5, -5

1, 2, 3

Output: 5, 5, 5

-5, -5, -5

Explanation: The sub-matrix with the sum closest to 0 is the entire input matrix itself.

Example 4

Input:   0, 0, 0, 0

0, 0, 0, 0

0, 0, 0, 0

Output:   0, 0, 0, 0

0, 0, 0, 0

0, 0, 0, 0

## Approach 1: Using HashMap Approach

The HashMap is used to store prefix sums along with their corresponding indices. The HashMap is used to find the largest rectangular sub-matrix whose sum is 0.

Algorithm

Step 1: Initialize maxArea to Integer.MIN_VALUE and variables for boundaries (upBound, downBound, leftBound, rightBound).

Step 2: Iterate through all possible left and right columns of the sub-matrix.

Step 3: For each pair of left and right columns, calculate the prefix sums of rows within these columns.

Step 4: Using a function findZeroSumSubarray to find the largest subarray with a sum of zero in the prefix sums.

Step 5: Update maxArea and boundaries if a larger sub-matrix with a zero sum is found.

Step 6: After iteration, if no valid sub-matrix is found, print "No zero-sum sub-matrix exists".

Step 7: Otherwise, print the elements of the largest sub-matrix with a zero sum.

FileName: LargestSubMatrixSumZero.java

import java.util.*;

public class LargestSubMatrixSumZero {

static final int MAX_ROWS = 100;

// Function to find the largest subarray with sum zero

static boolean findZeroSumSubarray(int[] array, int[] start, int[] end, int size) {

Map<Integer, Integer> prefixSums = new HashMap<>();

int sum = 0;

int maxLength = 0;

for (int i = 0; i < size; i++) {

sum += array[i];

// Check if current element is zero and no other zero element found yet

if (array[i] == 0 && maxLength == 0) {

start[0] = i;

end[0] = i;

maxLength = 1;

}

// Check if current sum is zero

if (sum == 0) {

if (maxLength < i + 1) {

start[0] = 0;

end[0] = i;

}

maxLength = i + 1;

}

// Check if current sum has been seen before

if (prefixSums.containsKey(sum)) {

int oldMaxLength = maxLength;

maxLength = Math.max(maxLength, i - prefixSums.get(sum));

if (oldMaxLength < maxLength) {

end[0] = i;

start[0] = prefixSums.get(sum) + 1;

}

} else {

prefixSums.put(sum, i);

}

}

return (maxLength != 0);

}

// Function to find the largest rectangular sub-matrix with zero sum

static void findLargestSubMatrixWithZeroSum(int[][] matrix, int rows, int cols) {

int[] temp = new int[rows];

int upBound = 0, downBound = 0, leftBound = 0, rightBound = 0;

int maxArea = Integer.MIN_VALUE;

for (int left = 0; left < cols; left++) {

Arrays.fill(temp, 0);

for (int right = left; right < cols; right++) {

for (int i = 0; i < rows; i++) {

temp[i] += matrix[i][right];

}

int[] up = new int[1];

int[] down = new int[1];

boolean found = findZeroSumSubarray(temp, up, down, rows);

int area = (down[0] - up[0] + 1) * (right - left + 1);

if (found && area > maxArea) {

upBound = up[0];

downBound = down[0];

leftBound = left;

rightBound = right;

maxArea = area;

}

}

}

// If no valid sub-matrix is found, print a message

if (upBound == 0 && downBound == 0 && leftBound == 0 && rightBound == 0 && matrix[0][0] != 0) {

System.out.println("No zero-sum sub-matrix exists");

return;

}

// Print the elements of the largest sub-matrix with zero sum

for (int i = upBound; i <= downBound; i++) {

for (int j = leftBound; j <= rightBound; j++) {

System.out.print(matrix[i][j] + " ");

}

System.out.println();

}

}

public static void main (String [] args) {

// Input matrix

int[][] matrix = {

{5, 5, 5},

{-5, -5, -5},

{1, 2, 3},

};

// number of rows and cols

int numRows = 3;

int numCols = 3;

findLargestSubMatrixWithZeroSum(matrix, numRows, numCols); // calling the method

}

}

Output

5 5 5

-5 -5 -5

Time Complexity: The algorithm has a time complexity of O(N^3), where N is the maximum of the number of rows or columns in the matrix. This complexity arises from the nested loops used to iterate through the matrix and compute prefix sums.

Space Complexity: The space complexity is O(N), where N is the maximum of the number of rows or columns. This space is primarily used to store the prefix sums in the HashMap and other variables such as arrays for tracking sub-matrix boundaries.

## Approach 2: Using Dynamic Programming Approach

The Dynamic Programming is used to find the largest rectangular sub-matrix whose sum is 0.

Algorithm

Step 1: Create a 2D array dp of size (rows + 1) x (cols + 1) to store prefix sums.

Step 2: Initialize variables for the bounds of the largest sub-matrix: upBound, downBound, leftBound, rightBound, and maxArea.

Step 3: The dp array by iterating through the matrix and calculating cumulative sums.

Step 4: dp[i][j] stores the sum of the sub-matrix from (0, 0) to (i-1, j-1).

Step 5: Iterate through all possible sub-matrices using four nested loops (indices i, k, l, r).

Step 6: Calculate the sum of each sub-matrix using dp.

Step 7: If the sum is zero, calculate the area and update maxArea and the bounds of the largest sub-matrix if necessary.

Step 8: If no valid sub-matrix is found, print "No zero-sum sub-matrix exists".

Step 9: Otherwise, print the elements of the largest sub-matrix with zero sum.

FileName: LargestSubMatrixSumZeroDP.java

import java.util.*;

public class LargestSubMatrixSumZeroDP {

// Function to find the largest sub-matrix with zero sum

static void findLargestSubMatrixWithZeroSum(int[][] matrix, int rows, int cols) {

// Initialize a 2D array to store prefix sums

int[][] dp = new int[rows + 1][cols + 1];

// Initialize variables for bounds and maximum area

int upBound = 0, downBound = 0, leftBound = 0, rightBound = 0;

int maxArea = Integer.MIN_VALUE;

// Calculate prefix sums

for (int i = 1; i <= rows; i++) {

for (int j = 1; j <= cols; j++) {

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];

}

}

// Iterate through all possible sub-matrices

for (int i = 0; i < rows; i++) {

for (int k = i + 1; k <= rows; k++) {

for (int l = 0; l < cols; l++) {

for (int r = l + 1; r <= cols; r++) {

// Compute sum of current sub-matrix using prefix sums

int sum = dp[k][r] - dp[i][r] - dp[k][l] + dp[i][l];

// If sum is zero, update maximum area and bounds

if (sum == 0) {

int area = (k - i) * (r - l);

if (area > maxArea) {

upBound = i;

downBound = k - 1;

leftBound = l;

rightBound = r - 1;

maxArea = area;

}

}

}

}

}

}

// If no valid sub-matrix is found, print a message

if (upBound == 0 && downBound == 0 && leftBound == 0 && rightBound == 0 && matrix[0][0] != 0) {

System.out.println("No zero-sum sub-matrix exists");

return;

}

// Print the elements of the largest sub-matrix with zero sum

for (int i = upBound; i <= downBound; i++) {

for (int j = leftBound; j <= rightBound; j++) {

System.out.print(matrix[i][j] + " ");

}

System.out.println();

}

}

public static void main (String [] args) {

// Test matrix

int[][] matrix = {

{5, 5, 5},

{-5, -5, -5},

{1, 2, 3},

};

// number of rows and cols

int numRows = 3;

int numCols = 3;

findLargestSubMatrixWithZeroSum(matrix, numRows, numCols); // calling the function

}

}

Output

5 5 5

-5 -5 -5

Time Complexity: The algorithm has a time complexity of O(N^3), where N is the maximum of the number of rows or columns in the matrix.

Space Complexity: The space complexity is O(N), where N is the maximum of the number of rows or columns.