Last Updated: 2 Jan, 2021

Largest Submatrix with Equal Number of 0's and 1's

Moderate

Asked in company

Solve now

Problem statement

You have been given a non-empty grid ‘MAT’ consisting of only 0s and 1s. Your task is to find the area of the largest sub-matrix having an equal number of 0s and 1s.

If there is no such sub-matrix, print 0.

For example, for the following grid:

Input

The largest sub-matrix having an equal number of 0s and 1s in the above grid is shown below :

Output

The area of the largest sub-matrix having an equal number of 0s and 1s is 4(rows in highlighted image) * 2(columns in highlighted image) = 8.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains two single space-separated integers ‘N’ and ‘M’ representing the number of rows and columns of the grid, respectively.

The next 'N' lines of each test case contain 'M' single space-separated integers 0 or 1.

Output Format:

For each test case, print the area of the largest possible sub-matrix having an equal number of 0s and 1s. 

Print the output of each test case in a separate line.

Note

You don’t have to print anything, it has already been taken care of. Just complete the function.

Constraints:

1 <= T <= 10^2
1 <= N <= 50
1 <= M <= 50
MAT[i][j] = 0 or 1

Time Limit: 1 sec

Solve now

Approaches

01 Approach

We will naively count 0s and 1s in all possible submatrices and return the area of the largest submatrix having an equal number of 0s and 1s.

Solve now

02 Approach

We will replace all 0s in the matrix by -1. Now we will find the submatrices with 0 sum and return the area of largest of them. A matrix with 0 sum has equal number of -1s and 1s, i.e. equal number of 0s and 1s.

We will use the prefix sum of the grid to calculate the sum of elements of a sub-matrix in O(1) time complexity.

Solve now

03 Approach

In this approach, we fix the left and right columns one by one and find the largest sub-array with contiguous rows sum 0 for every left and right column pair. Simply, we are finding the maximum length (top and bottom row) having sum 0 for every left and right column pair.

Here is the algorithm:

We will replace all 0’s of the matrix by -1.
We initialize an array ‘TEMP’ of size ‘N’ and an integer variable ‘MAXAREA’. Here ‘TEMP[i]’ denotes the sum of elements from left to right in a row ‘i’.
We iterate over each pair of columns.
Run a loop from 0 to ‘N’ and do ‘TEMP[i]’ = ‘MAT[i][right]’.
Now, we find the largest subarray with sum 0 in ‘TEMP’ using the function ‘sumZero’. The ‘sumZero’ function works as follows :
- We initialise a Hashmap ‘PREFIXSUMPOSITION’ and an integer variable ‘MAXLENGTH’ which stores the position of the prefix sum and maximum length of subarray having sum 0, respectively.
- We insert ‘PREFIXSUMPOSITION[0]’ = -1, because sum is 0 if present at index -1.
- Now we iterate over the ‘TEMP’ array and store the prefix sum in a variable ‘SUM’.
  - If ‘PREFIXSUMPOSITION.find(SUM)’ == ‘PREFIXSUMPOSITION.end()’:
    - ‘PREFIXSUMPOSITION[SUM]’ = ‘i’.
  - Else:
    - Update the ‘MAXLENGTH’ by a maximum of ‘i - PREFIXSUMPOSITION[sum]’ and ‘MAXLENGTH’.
- Finally, return ‘MAXLENGTH’.
Update ‘MAXAREA’ by a maximum of ‘MAXAREA’ and multiplication of length returned by ‘sumZero’ and breadth given by ‘right’ - ‘left’ + 1.
Finally, return ‘MAXAREA’.

Solve now