New update is available. Click here to update.

Sub-Matrix with Sum Zero

Posted: 4 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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 :

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