Maximum sub-matrix area having count of 1’s one more than count of 0’s in C++

In this tutorial, we will be discussing a program to find maximum sub-matrix area having count of 1’s one more than count of 0’s.

For this we will be provided with a matrix containing 0’s and 1’s. Our task is to get the sub-matrix of maximum area containing more 1’s than 0’s

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; #define SIZE 10 //finding length of longest sub-matrix int lenOfLongSubarr(int arr[], int n, int& start, int& finish) {    unordered_map<int, int> um;    int sum = 0, maxLen = 0;    for (int i = 0; i < n; i++) {       sum += arr[i];       if (sum == 1) {          start = 0;          finish = i;          maxLen = i + 1;       }       else if (um.find(sum) == um.end()) um[sum] = i;       if (um.find(sum - 1) != um.end()) {          if (maxLen < (i - um[sum - 1])) start = um[sum - 1] + 1;          finish = i;          maxLen = i - um[sum - 1];       }    }    return maxLen; } //finding the maximum area void largestSubmatrix(int mat[SIZE][SIZE], int n) {    int finalLeft, finalRight, finalTop, finalBottom;    int temp[n], maxArea = 0, len, start, finish;    for (int left = 0; left < n; left++) {       memset(temp, 0, sizeof(temp));       for (int right = left; right < n; right++) {          for (int i = 0; i < n; ++i)          temp[i] += mat[i][right] == 0 ? -1 : 1;          len = lenOfLongSubarr(temp, n, start, finish);          if ((len != 0) && (maxArea < (finish - start + 1) * (right - left + 1))) {             finalLeft = left;             finalRight = right;             finalTop = start;             finalBottom = finish;             maxArea = (finish - start + 1) * (right - left + 1);          }       }    }    cout << "(Top, Left): (" << finalTop << ", " << finalLeft << ")\n";    cout << "(Bottom, Right): (" << finalBottom << ", " << finalRight << ")\n";    cout << "Maximum area: " << maxArea; } int main() {    int mat[SIZE][SIZE] = {       { 1, 0, 0, 1 },       { 0, 1, 1, 1 },       { 1, 0, 0, 0 },       { 0, 1, 0, 1 }    };    int n = 4; largestSubmatrix(mat, n);    return 0; }

Output

(Top, Left): (1, 1) (Bottom, Right): (3, 3) Maximum area: 9