Largest Sub-Matrix With Equal 0’s And 1’s

Hard
0/120
profile
Contributed by
12 upvotes
Asked in companies
AmazonCodenationGoogle inc

Problem statement

You are given a matrix ‘ARR’ of size N * M. Each entry in this matrix is either 0 or 1.

Find the largest area of a rectangular sub-matrix that has an equal number of 0’s and 1’s in it.

Example : 
If ‘N’ = 4 and ‘M’ = 5, and the matrix is:
0 1 0 1 1
0 1 0 1 0
0 1 0 1 1
0 1 0 1 1

Then clearly, the submatrix containing all the elements of the first four columns contains has equal number of 0’s and 1’s, the area of this submatrix is equal to 4 * 4 = 16, therefore we will print 16.
Follow Up : 
Try to solve it in less than O( N^2 * M^2 ) time complexity.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains two integers ‘N’ and ‘M’, denoting the number of rows and columns in the matrix.

The next N lines, each contain M integers ‘ARR’, denoting the elements of the current row.
Output Format : 
For each test case, print the area of the largest sub-matrix that contains equal 0’s and 1’s.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ ‘T’ ≤ 10      
1 ≤ N, M ≤ 10
0 ≤ ARR[i][j] ≤ 1 

Time limit: 1 sec
Sample Input 1 :
2
4 5
0 1 0 1 1
0 1 0 1 0
0 1 0 1 1
0 1 0 1 1
4 5
0 0 1 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
Sample Output 1 :
16
2
Explanation For Sample Input 1 :
For test case 1 :
We will print 16 because:
The submatrix containing all the elements of the first four columns contains has equal number of 0’s and 1’s, the area of this submatrix is equal to 4 * 4 = 16, therefore we will print 16.

For test case 2 : 
We will print 2 because:
The submatrix containing ARR[0][1] and ARR[0][2] is the largest possible submatrix that contains equal number of 0’s and 1’s, the area of this submatrix is 1 * 2 = 2, therefore we will print 2.
Sample Input 2 :
2
1 1
1
1 4
1 0 1 0
Sample Output 2 :
0
4
Hint

Try to check the condition for all the submatrices possible. Replace 0’s by -1’s to make the problem simpler. 

Approaches (2)
Brute Force

A naive approach is to generate all the submatrices. We can fix the top left and bottom right ends of the submatrices to generate all the submatrices of the original input matrix. Note that each end has ~O(N*M) options, so in total just to generate the matrices takes approx ~O((N*M)*(N*M)) operations. Now for each submatrix generated we can count the number of 0’s and 1’s in it, and we can finally output the area of the submatrix that had the largest size and also had an equal number of 0's and 1's.

 

We may simply check for the sum of the submatrix equal to half of the total elements in the submatrix, or a clever approach can be to replace 0’s by -1’s and we now need to simply check if the submatrix sum is equal to zero, to check for the condition of equal 0’s and 1’s.

 

Note that this approach can be further optimised using the prefix sum of a 2D matrix. This approach involves precomputing the prefix matrix. This further helps us to find the sum of a submatrix in constant time, though the precomputation takes O(N*M) time, all the following followups to calculate the sum of the submatrix require only constant time. We have not discussed the implementation of this approach here as finding all the submatrices in this approach still takes ~O((N*M)*(N*M)) computations.

 

The steps are as follows :

  1. Initialize a variable ‘maxArea’ equal to 0, this variable stores our final answer.
  2. Runner a for loop for variable ‘TopR’ from 0 to N-1, run an inner for loop for the variable ‘TopC’ from 0 to M-1, run the third loop for variable ‘BottomR’ from TopR to N-1, and run the fourth loop for variable ‘BottomC’ from TopC to M-1. Here (TopR, TopC) denotes the top-left cell of our submatrix and (BottomR, BottomC) denotes the bottom-right cell. Inside this:
    • Iterate all the elements of the submatrix to count the number of 0’s and 1’s. Store these counts in two variables and finally check if they are equal then update the value of ‘maxArea’ if needed.
  3. Finally, return the value stored in ‘maxArea’.
Time Complexity

O( ( N ^ 3 ) * ( M ^ 3 ) ), where N denotes the number of rows and M denotes the number of columns.

 

Generating all the submatrices takes ~((N*M)*(N*M)) operations and for each generated submatrix we take ~O(N*M) time to calculate the sum of that submatrix.

Hence the time complexity is O( ( N^3 )*(M^3) ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Largest Sub-Matrix With Equal 0’s And 1’s
Full screen
Console