Table of Contents
Problem Statement
Find the maximum size sub-matrix in a 2D array whose sum is zero. A sub-matrix is nothing but a 2D array inside of the given 2D array. So, you have a matrix of signed integers, you need to calculate the sum of sub-matrices and find the matrix with maximum size whose sum is zero.
Example
Matrix = { 0 10 0
-20 10 100
10 -100 -10 }
9
Explanation: Here, in this given input we have only one possible answer. We can choose a sub-matrix of size 9(whole matrix) which will be the maximum size sub-matrix. So, we shall choose entire matrix as the answer.
Matrix = { 100
-100
100 }2
Explanation: There are two options to choose from. Either you choose first and second row or second and third row. Both of them will result into sum = 0.
Approach to find largest rectangular sub-matrix whose sum is 0
Naive Approach
We can take care of this issue by utilizing a simple arrangement. We can utilize four indices each for various cells of the matrix. Out of these indices, one will be for a beginning row, beginning column, finishing row, and finishing column. We can utilize a 2D prefix sum approach for slightly improving our solution. This methodology can optimize our simple solution a little yet that won’t be enough, however.
Efficient Approach
So, we will use a similar approach as we did with the problem Find sub-matrix with maximum Sum. We will now fix two columns, one for the left column and one for the right column. For storing the sums between these columns for each of the rows from starting 0th row to the end row (n-1th), we will create a temporary array. Now, we will make use of map data structure for storing the indices for sums encountered until now.
Just to get a hang of this approach, you can consider a 1D array of prefix sums, and if we find two same values in the prefix sum array. That means we have two indices until which the sum of elements is the same. So, if we subtract the sum at a smaller index from the sum at a higher index. We get the sum between the smaller index and the higher index. Since both of those values were equal. We are left with sum = 0. The same thing is what we are doing here.
Code for finding the largest rectangular sub-matrix whose sum is 0
C++ Code
#include<bits/stdc++.h>
using namespace std;
int findMaximumSubMatrixWithZeroSum(vector<vector<int>> matrix, int n, int m){
// stores the prefixSum of rows
vector<vector<int>> prefixSum(n,vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
prefixSum[i][j] = matrix[i][j];
}
// calculation prefix sum for each row
for(int i=0;i<n;i++){
for(int j=1;j<m;j++)
prefixSum[i][j] += prefixSum[i][j-1];
}
// store indices of submatrix with maximum sum
int startCol = 0, endCol = 0, startRow = 0, endRow = 0;
int maxSize = 0;
// use a map to first store the row for sum if it was not present earlier
// else we calculate the result regarding the particular sum
for(int firstCol=0;firstCol<m;firstCol++){
for(int secondCol=firstCol;secondCol<m;secondCol++){
int tmp[n]; // stores the sum between two columns for each row
for(int row=0;row<n;row++)
tmp[row] = prefixSum[row][secondCol] - (firstCol>0 ? prefixSum[row][firstCol-1] : 0);
int curSum = 0;
unordered_map<int,int> rowSumMap;
rowSumMap[0] = -1;
for(int curRow=0;curRow<n;curRow++){
curSum += tmp[curRow];
if(rowSumMap.count(curSum)) {
int subMatrixSize = (secondCol - firstCol + 1)*(curRow - rowSumMap[curSum]);
if(subMatrixSize > maxSize){
maxSize = subMatrixSize;
startCol = firstCol;
endCol = secondCol;
startRow = rowSumMap[curSum] + 1;
endRow = curRow;
}
} else {
rowSumMap[curSum] = curRow;
}
}
}
}
if(maxSize == 0){
cout<<"There exists no sub-matrix with zero sum"<<endl;
return 0;
}
cout<<"Sub-matrix with zero Sum"<<endl;
for(int i=startRow;i<=endRow;i++){
for(int j=startCol;j<=endCol;j++){
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
return maxSize;
}
int main(){
int t;cin>>t;
while(t--){
int n,m;cin>>n>>m;
vector<vector<int>> matrix(n,vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
cin>>matrix[i][j];
}
int ans = findMaximumSubMatrixWithZeroSum(matrix, n, m);
if(ans != 0)
cout<<ans<<endl;
}
}
2 4 4 5 9 8 7 -9 -5 -4 -2 0 0 0 -9 1 8 8 4 4 4 5 9 8 7 -9 -5 -4 -2 0 0 0 9 1 8 8 4
Largest Sub-matrix with zero Sum 5 9 8 7 -9 -5 -4 -2 0 0 0 -9 12 Largest Sub-matrix with zero Sum 5 9 -9 -5 0 0 6
Java Code
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
static int findMaximumSubMatrixWithZeroSum(int[][] matrix, int n, int m){
// stores the prefixSum of rows
int[][] prefixSum = new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
prefixSum[i][j] = matrix[i][j];
}
// calculation prefix sum for each row
for(int i=0;i<n;i++){
for(int j=1;j<m;j++)
prefixSum[i][j] += prefixSum[i][j-1];
}
int startCol = 0, endCol = 0, startRow = 0, endRow = 0;
int maxSize = 0;
for(int firstCol=0;firstCol<m;firstCol++){
for(int secondCol=firstCol;secondCol<m;secondCol++){
int tmp[] = new int[n]; // stores the sum between two columns for each row
for(int row=0;row<n;row++)
tmp[row] = prefixSum[row][secondCol] - (firstCol>0 ? prefixSum[row][firstCol-1] : 0);
int curSum = 0;
HashMap<Integer, Integer> rowSumMap = new HashMap<Integer, Integer>();
rowSumMap.put(0,-1);
for(int curRow=0;curRow<n;curRow++){
curSum += tmp[curRow];
if(rowSumMap.containsKey(curSum)) {
int subMatrixSize = (secondCol - firstCol + 1)*(curRow - rowSumMap.get(curSum));
if(subMatrixSize > maxSize){
maxSize = subMatrixSize;
startCol = firstCol;
endCol = secondCol;
startRow = rowSumMap.get(curSum) + 1;
endRow = curRow;
}
} else {
rowSumMap.put(curSum,curRow);
}
}
}
}
if(maxSize == 0){
System.out.println("There exists no sub-matrix with zero sum");
return 0;
}
System.out.println("Largest Sub-matrix with zero Sum");
for(int i=startRow;i<=endRow;i++){
for(int j=startCol;j<=endCol;j++){
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}
return maxSize;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0){
int n = sc.nextInt();
int m = sc.nextInt();
int matrix[][] = new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
matrix[i][j] = sc.nextInt();
}
int ans = findMaximumSubMatrixWithZeroSum(matrix, n, m);
if(ans != 0)
System.out.println(ans);
}
}
}2 4 4 5 9 8 7 -9 -5 -4 -2 0 0 0 -9 1 8 8 4 4 4 5 9 8 7 -9 -5 -4 -2 0 0 0 9 1 8 8 4
Largest Sub-matrix with zero Sum 5 9 8 7 -9 -5 -4 -2 0 0 0 -9 12 Largest Sub-matrix with zero Sum 5 9 -9 -5 0 0 6
Complexity Analysis
Time Complexity: O(N^3)
We have a polynomial-time complexity of O(N^3) because there are three nested loops. One loop is used for finding the zero Sum using prefix Sum and map technique.
Space Complexity: O(N^2)
Since we made a 2D prefix Sum array. We have space complexity of O(N^2).