Maximum Sub-Matrix Area with Count of 1s One More than Count of 0s in C++

In this problem, we are given a 2-D matrix of size nXn consisting of binary numbers (0/1). Our task is to create a program to find the Maximum submatrix area having count of 1’s one more than count of 0’s.

Let’s take an example to understand the problem,

Input

bin[N][N] = {
   {0, 1, 0, 0},
   {1, 1, 0, 0},
   {1, 0, 1, 1},
   {0, 1, 0, 1}
}

Output

9

Explanation

submatrix :
bin[1][0], bin[1][1], bin[1][2]
bin[2][0], bin[2][1], bin[2][2]
bin[3][0], bin[3][1], bin[3][2]
is the largest subarray with more 1’s one more than 0’s.
Number of 0’s = 4
Number of 1’s = 5

Solution Approach

A simple approach is to find all submatrices possible from the matrix and then return the maximum area out of all.

This approach is easy to think and implement but takes a lot of time and requires nesting of loops that makes in time complexity of the order O(n^4). So, let’s discuss one more method which is more effective.

The idea here is to fix columns at the left and right of the matrix and then find the largest subarray which has the number of 0’s one more than the number of 1’s. We will calculate the sum at each row and then cumulate it. To find the maximum area having a count of 1’s one more than the number of 0’s.

Example

Program to illustrate the working of our solution,

 Live Demo

#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
int lenOfLongSubarr(int row[], int n, int& startInd, int& finishInd){
   unordered_map<int, int> subArr;
   int sumVal = 0, maxSubArrLen = 0;
   for (int i = 0; i < n; i++) {
      sumVal += row[i];
      if (sumVal == 1) {
         startInd = 0;
         finishInd = i;
         maxSubArrLen = i + 1;
      }
      else if (subArr.find(sumVal) == subArr.end())
         subArr[sumVal] = i;
      if (subArr.find(sumVal − 1) != subArr.end()) {
         int currLen = (i − subArr[sumVal − 1]);
         if (maxSubArrLen < currLen)
            startInd = subArr[sumVal − 1] + 1;
         finishInd = i;
         maxSubArrLen = currLen;
      }
   }
   return maxSubArrLen;
}
int largestSubmatrix(int bin[SIZE][SIZE], int n){
   int rows[n], maxSubMatArea = 0, currArea, longLen, startInd,
   finishInd;
   for (int left = 0; left < n; left++) {
      memset(rows, 0, sizeof(rows));
      for (int right = left; right < n; right++) {
         for (int i = 0; i < n; ++i){
            if(bin[i][right] == 0)
               rows[i] −= 1;
            else
               rows[i] += 1;
         }
         longLen = lenOfLongSubarr(rows, n, startInd, finishInd);
         currArea = (finishInd − startInd + 1) * (right − left + 1);
         if ((longLen != 0) && (maxSubMatArea < currArea)) {
            maxSubMatArea = currArea;
         }
      }
   }
   return maxSubMatArea;
}
int main(){
   int bin[SIZE][SIZE] = {
      { 1, 0, 0, 1 },
      { 0, 1, 1, 1 },
      { 1, 0, 0, 0 },
      { 0, 1, 0, 1 }
   };
   int n = 4;
   cout<<"The maximum sub−matrix area having count of 1’s one more
   than count of 0’s is "<<largestSubmatrix(bin, n);
   return 0;
}

Output

The maximum sub-matrix area having count of 1’s one more than count of
0’s is 9