Table of Contents
Problem Statement
Given a binary matrix of size n x m. The problem is to find the largest area rectangular sub-matrix with equal number of 1’s and 0’s.
Example
Dimensions = 4 x 4 Matrix: 1 1 1 1 0 1 0 1 1 0 1 0 1 0 0 0
12
Explanation: If we consider the submatrix with corners (0,1), (0,3), (3,1) and (3,3). This sub-matrix makes the largest rectangular sub-matix having equal number of 0s and 1s.
Dimesnions = 2 x 4 Matrix: 0 0 1 0 1 1
6
Explanation: Since the initial matrix had an equal number of 0s and 1s, then the initial matrix will be our answer. That’s the case here.
Approach
Naive Approach
The easiest thing that we can do, is considering four-pointers each for sub-matrix’s indices in all four directions. When we fixed the sub-matrix, we can count the number of 0s and 1s. But this is not an efficient approach and will surely exceed the time constraints. We can optimize the problem a bit if we change each 0 with a -1. Afterward, we find the sum of the sub-matrix using the 2D prefix sum technique. But even though using that won’t be enough.
Efficient Approach
An efficient approach will be to first change each 0 in the matrix with a negative 1. Afterward, the problem reduces to finding the largest sub-matrix having sum 0. We have already covered this problem. This problem is solved using dynamic programming. We fix the left and right columns. Then store the sum of elements of each row from the first column to the second column in a temporary array. Then we make a map, where we store row numbers corresponding to the sum of elements while traversing this temporary array. So, if we again encounter the same sum value in our temporary array. We are sure that if we consider the elements from the row, currently being stored in a map against the sum value to this current row, will have sum 0. And when we changed 0 to -1, we had converted from largest area rectangular sub-matrix with equal number of 1’s and 0’s problem to finding the largest sub-matrix having sum 0 and now we are done with that.
Code to find largest area rectangular sub-matrix with equal number of 1’s and 0’s
C++ Code
#include<bits/stdc++.h>
using namespace std;
int largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s (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 equal numbers of 0s and 1s"<<endl;
return 0;
}
cout<<"Largest Sub-matrix with equal number of 1s and 0s"<<endl;
for(int i=startRow;i<=endRow;i++){
for(int j=startCol;j<=endCol;j++){
cout<<(matrix[i][j]>0 ? 1 : 0)<<" ";
}
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];
matrix[i][j] = matrix[i][j] ? 1 : -1;
}
}
int ans = largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s(matrix, n, m);
if(ans != 0)
cout<<ans<<endl;
}
}
1 4 4 1 1 1 1 0 1 0 1 1 0 1 0 1 0 0 0
Largest Sub-matrix with equal number of 1s and 0s 1 1 1 1 0 1 0 1 0 0 0 0 12
Java Code
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
static int largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s (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 equal number of 1s and 0s");
return 0;
}
System.out.println("Largest Rectangular Sub-matrix with equal number of 1s and 0s");
for(int i=startRow;i<=endRow;i++){
for(int j=startCol;j<=endCol;j++){
System.out.print((matrix[i][j]>0) ? "1 " : "0 ");
}
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();
matrix[i][j] = matrix[i][j]>0 ? 1 : -1;
}
}
int ans = largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s (matrix, n, m);
if(ans != 0)
System.out.println(ans);
}
}
}1 4 4 1 1 1 1 0 1 0 1 1 0 1 0 1 0 0 0
Largest Rectangular Sub-matrix with equal number of 1s and 0s 1 1 1 1 0 1 0 1 0 0 0 0 12
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 the prefix Sum and map technique.
Space Complexity: O(N^2)
Since we made a 2D prefix Sum array. Thus, largest area rectangular sub-matrix with equal number of 1’s and 0’s problem has polynomial space complexity. We have space complexity of O(N^2).