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

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
12 upvotes
Asked in company
RedBus

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
2 2
1 0
0 0
Sample Output 1:
2
Explanation of the Sample Input 1:
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 2(rows in highlighted image) * 1(columns in highlighted image) = 2.
Sample Input 2:
2
3 4
1 1 1 1
0 1 1 0
0 0 0 0
2 3
0 0 0
0 0 1
Sample Output 2:
12
2
Explanation of the Sample Input 1:
For the first test case, the area of the largest sub-matrix having an equal number of 0s and 1s is the same as the area of the matrix as the matrix has 6 zeros and 6 ones.

For the second test case, the area of the largest sub-matrix having an equal number of 0s and 1s is 2 as we will take 1 zero and 1 one in the final matrix. Thus, area is 2 * 1 = 2.
Hint

Can you count 0s and 1s in all possible submatrices?

Approaches (3)
Naive 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.

Time Complexity

O((N * M) ^ 3), where N is the number of rows in the given grid, and M is the number of columns. 

 

Since we are iterating the grid for every possible start and end index. Hence, the time complexity is O((N * M) ^ 3).

Space Complexity

O(1)

 

Because we are not using any extra space for finding our answer.

Code Solution
(100% EXP penalty)
Largest Submatrix with Equal Number of 0's and 1's
Full screen
Console