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.
![Largest rectangular sub-matrix whose sum is 0 in Java/>
<!-- /wp:html -->
<!-- wp:paragraph -->
<p><strong>Example 1</strong></p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p><strong>Input:</strong> 9, 7,16, 5</p>
<!-- /wp:paragraph -->
<!-- wp:preformatted -->
<pre class=](https://static.tutorialandexample.com/java/largest-rectangular-sub-matrix-whose-sum-is-0-in-java1.png)
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) { MapprefixSums = 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.