Given a N x N binary matrix. The problem is finding the maximum area sub-matrix having a count of 1’s one more than count of 0’s.
Examples:
Input : mat[][] = { {1, 0, 0, 1},
{0, 1, 1, 1},
{1, 0, 0, 0},
{0, 1, 0, 1} }
Output : 9
The sub-matrix defined by the boundary values (1, 1) and (3, 3).
{ {1, 0, 0, 1},
{0, 1, 1, 1},
{1, 0, 0, 0},
{0, 1, 0, 1} }
Naive Approach: Check every possible rectangle in given 2D matrix. This solution requires 4 nested loops and the time complexity of this solution would be O(n^4).
Efficient Approach:
An efficient approach will be to use Longest subarray having count of 1s one more than count of 0s which reduces the time complexity to O(n^3). The idea is to fix the left and right columns one by one and find the maximum length contiguous rows having the count of 1’s one more than the count of 0’s for every left and right column pair.
Find top and bottom row numbers (which have a maximum length) for every fixed left and right column pair. To find the top and bottom row numbers, calculate the sum of elements in every row from left to right and store these sums in an array say temp[] (consider 0 as -1 while adding it). So temp[i] indicates the sum of elements from left to right in row i.
Using the approach in Longest subarray having count of 1s one more than count of 0s , temp[] array is used to get the maximum length subarray of temp[] having count of 1’s one more than a count of 0’s by obtaining the start and end row numbers, then these values can be used to find maximum possible area with left and right as boundary columns. To get the overall maximum area, compare this area with the maximum area so far.
Below is the implementation of the above approach:
C++
// C++ implementation to find// the maximum area sub-matrix// having count of 1's// one more than count of 0's#include <bits/stdc++.h>using namespace std;#define SIZE 10// function to find the length of longest// subarray having count of 1's one more// than count of 0'sint lenOfLongSubarr(int arr[], int n, int& start, int& finish){ // unordered_map 'um' implemented as // hash table unordered_map<int, int> um; int sum = 0, maxLen = 0; // traverse the given array for (int i = 0; i < n; i++) { // accumulating sum sum += arr[i]; // when subarray starts form index '0' if (sum == 1) { start = 0; finish = i; maxLen = i + 1; } // make an entry for 'sum' if it is // not present in 'um' else if (um.find(sum) == um.end()) um[sum] = i; // check if 'sum-1' is present in 'um' // or not if (um.find(sum - 1) != um.end()) { // update 'start', 'finish' // and maxLength if (maxLen < (i - um[sum - 1])) start = um[sum - 1] + 1; finish = i; maxLen = i - um[sum - 1]; } } // required maximum length return maxLen;}// function to find the maximum// area sub-matrix having// count of 1's one more than count of 0'svoid largestSubmatrix(int mat[SIZE][SIZE], int n){ // variables to store final // and intermediate results int finalLeft, finalRight, finalTop, finalBottom; int temp[n], maxArea = 0, len, start, finish; // set the left column for (int left = 0; left < n; left++) { // Initialize all elements of temp as 0 memset(temp, 0, sizeof(temp)); // Set the right column for the // left column set by outer loop for (int right = left; right < n; right++) { // Calculate sum between current left and right // for every row 'i', consider '0' as '-1' for (int i = 0; i < n; ++i) temp[i] += mat[i][right] == 0 ? -1 : 1; // function to set the 'start' and 'finish' // variables having index values of // temp[] which contains the longest // subarray of temp[] having count of 1's // one more than count of 0's len = lenOfLongSubarr(temp, n, start, finish); // Compare with maximum area // so far and accordingly update the // final variables 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); } } } // Print final values cout << "(Top, Left): (" << finalTop << ", " << finalLeft << ")\n"; cout << "(Bottom, Right): (" << finalBottom << ", " << finalRight << ")\n"; cout << "Maximum area: " << maxArea;}// Driver Codeint 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;} |
Java
// Java implementation to find// the maximum area sub-matrix// having count of 1's// one more than count of 0'simport java.util.*;class GFG{static int start, finish;// Function to find the length of longest// subarray having count of 1's one more// than count of 0'sstatic int lenOfLongSubarr(int []arr, int n){ // unordered_map 'um' implemented as // hash table HashMap<Integer,Integer> um = new HashMap<Integer, Integer>(); int sum = 0, maxLen = 0; // Traverse the given array for(int i = 0; i < n; i++) { // Accumulating sum sum += arr[i]; // When subarray starts form index '0' if (sum == 1) { start = 0; finish = i; maxLen = i + 1; } // Make an entry for 'sum' if it is // not present in 'um' else if (!um.containsKey(sum)) um.put(sum,i); // Check if 'sum-1' is present in 'um' // or not if (um.containsKey(sum - 1)) { // Update 'start', 'finish' // and maxLength if (maxLen < (i - um.get(sum - 1))) start = um.get(sum - 1) + 1; finish = i; maxLen = i - um.get(sum - 1); } } // Required maximum length return maxLen;}// Function to find the maximum// area sub-matrix having// count of 1's one more than count of 0'sstatic void largestSubmatrix(int [][]mat, int n){ // Variables to store final // and intermediate results int finalLeft = 0, finalRight = 0, finalTop = 0, finalBottom = 0; int maxArea = 0, len; finish = 0; start=0; int []temp = new int[n]; // Set the left column for(int left = 0; left < n; left++) { // Initialize all elements of temp as 0 Arrays.fill(temp, 0); // Set the right column for the // left column set by outer loop for(int right = left; right < n; right++) { // Calculate sum between current left // and right for every row 'i', // consider '0' as '-1' for(int i = 0; i < n; ++i) temp[i] += mat[i][right] == 0 ? -1 : 1; // Function to set the 'start' and 'finish' // variables having index values of // temp[] which contains the longest // subarray of temp[] having count of 1's // one more than count of 0's len = lenOfLongSubarr(temp, n); // Compare with maximum area // so far and accordingly update the // final variables 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); } } } // Print final values System.out.print("(Top, Left): (" + finalTop + ", " + finalLeft + ")\n"); System.out.print("(Bottom, Right): (" + finalBottom + ", " + finalRight + ")\n"); System.out.print("Maximum area: " + maxArea);}// Driver codepublic static void main(String[] args) { int [][]mat = new int[][]{ { 1, 0, 0, 1 }, { 0, 1, 1, 1 }, { 1, 0, 0, 0 }, { 0, 1, 0, 1 } }; int n = 4; largestSubmatrix(mat, n);}}// This code is contributed by pratham76 |
Python3
# Python implementation to find# the maximum area sub-matrix# having count of 1's# one more than count of 0's# function to find the length of longest# subarray having count of 1's one more# than count of 0'sdef lenOfLongSubarr(arr, n, start, finish): # unordered_map 'um' implemented as # hash table um = {} sum = 0 maxLen = 0 # traverse the given array for i in range(n): # accumulating sum sum += arr[i] # when subarray starts form index '0' if (sum == 1): start = 0 finish = i maxLen = i + 1 # make an entry for 'sum' if it is # not present in 'um' elif (sum not in um): um[sum] = i # check if 'sum-1' is present in 'um' # or not if (sum - 1 in um): # update 'start', 'finish' # and maxLength if (maxLen < (i - um[sum - 1])): start = um[sum - 1] + 1 finish = i maxLen = i - um[sum - 1] # required maximum length return [maxLen,start,finish]# function to find the maximum# area sub-matrix having# count of 1's one more than count of 0'sdef largestSubmatrix(mat, n): # variables to store final # and intermediate results temp = [] maxArea = 0 # set the left column for left in range(n): # Initialize all elements of temp as 0 temp = [0 for i in range(n)] # Set the right column for the # left column set by outer loop for right in range(left, n): # Calculate sum between current left and right # for every row 'i', consider '0' as '-1' for i in range(n): if mat[i][right] == 0: temp[i] -= 1 else: temp[i] += 1 # function to set the 'start' and 'finish' # variables having index values of # temp[] which contains the longest # subarray of temp[] having count of 1's # one more than count of 0's start = 0 finish = 0 fc = lenOfLongSubarr(temp, n, start, finish) len = fc[0] start = fc[1] finish = fc[2] # Compare with maximum area # so far and accordingly update the # final variables if ((len != 0) and (maxArea < (finish - start + 1) * (right - left + 1))): finalLeft = left finalRight = right finalTop = start finalBottom = finish maxArea = (finish - start + 1) * (right - left + 1) # Print final values print("(Top, Left): (",finalTop,", ",finalLeft,")") print("(Bottom, Right): (",finalBottom, ", ",finalRight,")") print("Maximum area: ", maxArea)# Driver Codemat = [[1, 0, 0, 1 ], [ 0, 1, 1, 1 ], [ 1, 0, 0, 0 ], [ 0, 1, 0, 1 ]]n = 4largestSubmatrix(mat, n)# This code is contributed by rohitsingh07052 |
C#
// C# implementation to find// the maximum area sub-matrix// having count of 1's// one more than count of 0'susing System;using System.Collections.Generic;using System.Collections;class GFG{// Function to find the length of longest// subarray having count of 1's one more// than count of 0'sstatic int lenOfLongSubarr(int []arr, int n, ref int start, ref int finish){ // unordered_map 'um' implemented as // hash table Dictionary<int, int> um = new Dictionary<int, int>(); int sum = 0, maxLen = 0; // Traverse the given array for(int i = 0; i < n; i++) { // Accumulating sum sum += arr[i]; // When subarray starts form index '0' if (sum == 1) { start = 0; finish = i; maxLen = i + 1; } // Make an entry for 'sum' if it is // not present in 'um' else if (!um.ContainsKey(sum)) um[sum] = i; // Check if 'sum-1' is present in 'um' // or not if (um.ContainsKey(sum - 1)) { // Update 'start', 'finish' // and maxLength if (maxLen < (i - um[sum - 1])) start = um[sum - 1] + 1; finish = i; maxLen = i - um[sum - 1]; } } // Required maximum length return maxLen;} // Function to find the maximum// area sub-matrix having// count of 1's one more than count of 0'sstatic void largestSubmatrix(int [,]mat, int n){ // Variables to store final // and intermediate results int finalLeft = 0, finalRight = 0, finalTop = 0, finalBottom = 0; int maxArea = 0, len, start = 0, finish = 0; int []temp = new int[n]; // Set the left column for(int left = 0; left < n; left++) { // Initialize all elements of temp as 0 Array.Fill(temp, 0); // Set the right column for the // left column set by outer loop for(int right = left; right < n; right++) { // Calculate sum between current left // and right for every row 'i', // consider '0' as '-1' for(int i = 0; i < n; ++i) temp[i] += mat[i, right] == 0 ? -1 : 1; // Function to set the 'start' and 'finish' // variables having index values of // temp[] which contains the longest // subarray of temp[] having count of 1's // one more than count of 0's len = lenOfLongSubarr(temp, n, ref start, ref finish); // Compare with maximum area // so far and accordingly update the // final variables 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); } } } // Print final values Console.Write("(Top, Left): (" + finalTop + ", " + finalLeft + ")\n"); Console.Write("(Bottom, Right): (" + finalBottom + ", " + finalRight + ")\n"); Console.Write("Maximum area: " + maxArea); }// Driver codepublic static void Main(string[] args) { int [,]mat = new int[,]{ { 1, 0, 0, 1 }, { 0, 1, 1, 1 }, { 1, 0, 0, 0 }, { 0, 1, 0, 1 } }; int n = 4; largestSubmatrix(mat, n);}}// This code is contributed by rutvik_56 |
Javascript
<script>// JavaScript implementation to find// the maximum area sub-matrix// having count of 1's// one more than count of 0's// function to find the length of longest// subarray having count of 1's one more// than count of 0'sfunction lenOfLongSubarr(arr, n, start, finish){ // unordered_map 'um' implemented as // hash table let um = new Map() let sum = 0 let maxLen = 0 // traverse the given array for(let i=0;i<n;i++){ // accumulating sum sum += arr[i] // when subarray starts form index '0' if (sum == 1){ start = 0 finish = i maxLen = i + 1 } // make an entry for 'sum' if it is // not present in 'um' else if (um.has(sum) == false) um.set(sum,i) // check if 'sum-1' is present in 'um' // or not if (um.has(sum - 1)){ // update 'start', 'finish' // and maxLength if (maxLen < (i - um.get(sum - 1))){ start = um.get(sum - 1) + 1 finish = i maxLen = i - um.get(sum - 1) } } } // required maximum length return [maxLen,start,finish]}// function to find the maximum// area sub-matrix having// count of 1's one more than count of 0'sfunction largestSubmatrix(mat, n){ // variables to store final // and intermediate results let temp = [] let maxArea = 0 let finalLeft,finalRight,finalTop,finalBottom; // set the left column for(let left=0;left<n;left++){ // Initialize all elements of temp as 0 temp = new Array(n).fill(0) // Set the right column for the // left column set by outer loop for(let right = left;right<n;right++){ // Calculate sum between current left and right // for every row 'i', consider '0' as '-1' for(let i=0;i<n;i++){ if(mat[i][right] == 0) temp[i] -= 1 else temp[i] += 1 } // function to set the 'start' and 'finish' // variables having index values of // temp[] which contains the longest // subarray of temp[] having count of 1's // one more than count of 0's let start = 0 let finish = 0 let fc = lenOfLongSubarr(temp, n, start, finish) let len = fc[0] start = fc[1] finish = fc[2] // Compare with maximum area // so far and accordingly update the // final variables 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) } } } // Print final values document.write("(Top, Left): (" + finalTop + ", " + finalLeft + ")","</br>") document.write("(Bottom, Right): (" + finalBottom + ", " + finalRight + ")","</br>") document.write("Maximum area: "+ maxArea,"</br>")}// Driver Codelet mat = [[1, 0, 0, 1 ], [ 0, 1, 1, 1 ], [ 1, 0, 0, 0 ], [ 0, 1, 0, 1 ]]let n = 4largestSubmatrix(mat, n)// This code is contributed by shinjanpatra</script> |
Output
(Top, Left): (1, 1) (Bottom, Right): (3, 3) Maximum area: 9
Complexity Analysis:
- Time Complexity: O(N3).
- Auxiliary Space: O(N).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
