Sub-Matrix with Sum Zero
Given a 2-dimensional matrix of size ‘N’ x ‘M’. Find the size of the largest sub-matrix whose sum is equal to 0. The size of a matrix is the product of rows and columns in it.
A sub-matrix is a matrix obtained from the given matrix by deletion of several (possibly, zero or all) rows/columns from the beginning and several (possibly, zero or all) rows/columns from the end.
For example :
If there is no sub-matrix with sum equal to 0, then return 0.
Input Format
The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.
The first line of each test case contains two single-spaced integers 'N' and 'M', representing the number of rows and columns of the matrix, respectively.
The next 'N' lines contain 'M' single-spaced integers denoting matrix elements.
Output Format:
For each test case, in the first line, print an integer denoting the size of the largest sub-matrix with sum equal to 0.
The output of each test case is printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N, M <= 50
-10^5 <= data <= 10^5,
Where ‘data’ is the value of the elements of the matrix.
Time Limit: 1 sec
In this approach, we will find all possible sub-matrices and check whether it has sum equal to zero or not.
We will define a sub-matrix using 4 variables ('R1', ‘C1’, ‘R2’, ‘C2’). ('R1', ‘C1’) denotes the top-left corner of the sub-matrix and ('R2', ‘C2’) denotes the bottom-right corner of the sub-matrix.
For ('R1': 0 to ‘N-1’){
For ('C1': 0 to 'M-1'){
For('R2': ‘R1’ to ‘N-1’){
For ('C2': 'C2' to 'M-1'){
Find the sum of sub-matrix ('R1', ‘C1’, ‘R2’, ‘C2’)
}
}
}
}
For finding the sum of a sub-matrix, we will iterate on the elements of the sub-matrix using two loops.
In this approach, we will use the prefix sum, so that we don’t have to iterate on the elements of sub-matrix for finding the sum of a sub-matrix.
Let ‘PREF[][]' store the prefix sum of the given matrix.
‘PREF[i][j]’ is the sum of the sub-matrix whose top-left corner is at (0, 0) and bottom right corner is at ('i', ‘j’).
For finding the prefix matrix, first, we will do the row-wise sum and then we will do the column-wise sum.
For example:
Sum of a sub-matrix ('R1', ‘C1’, ‘R2’, ‘C2’) {where ('R1', ‘C1’) denotes the top-left corner of the sub-matrix and ('R2', ‘C2’) denotes the bottom-right corner of the sub-matrix} is:
‘SUM’ = 'PREF[R2][C2]' - ‘PREF[R2][C1-1]’ - ‘PREF[R1-1][C2]’ + ‘PREF[R1-1][C1-1]’.
We will define a sub-matrix using 4 variables ('R1', ‘C1’, ‘R2’, ‘C2’). ('R1', ‘C1’) denotes the top-left corner of the sub-matrix and ('R2', ‘C2’) denotes the bottom-right corner of the sub-matrix.
In this approach, we will fix ‘C1’, ‘C2’ and ‘R2’ and find if there is any possible ‘R1’ such that the sum of sub-matrix ('R1', ‘C1’, ‘R2’, ‘C2’) is 0. If there are multiple possible values of ‘R1’ then we will pick ‘R1’ which is the smallest (because the smallest ‘R1’ will give the largest sub-matrix).
Let’s say we have two columns ‘C1’ and ‘C2’ ('C1' <= ‘C2’) and we want to find a sub-matrix which has ‘C1’ and ‘C2’ as its column ends and sum equal to zero.
Make an array ‘SUM’ of size ‘N’ where ‘SUM[i]’ is equal to the sum of elements in row ‘i’ from column ‘C1’ to ‘C2’.
Now, the problem is reduced to finding the largest subarray of the ‘SUM’ array which has sum equal to zero.
How to find the largest subarray with sum equal to zero?
Let’s consider an array {5, -2, 1, 3, -4, 2}, its ‘SUM’ array will be {5, 3, 4, 7, 3, 5}.
In this array there are two subarrays {1, 3, -4} and {-2, 1, 3, -4, 2} which has sum equal to zero.
Make a hash table, where ‘SUM[i]' is the key and it has value 'i'.
Now, iterate over the 'SUM' array and for each index ‘i’:
- If ‘SUM[i]’ is present in the hash table:
- Let’s say its value is ‘j’, then there is a subarray from index ‘j+1’ to ‘i’ which has sum equal to 0, because ‘SUM[i]’ - ‘SUM[j]’ = 0 ( ‘arr[j+1]’ + ... + 'arr[i]' = 0).
- Else, insert {'SUM[i]', ‘i’} pair in the hash table.
