Problem of the day
You are given an 'N' * 'M' size binary-valued matrix, where 'N' is the number of rows and 'M' is the number of columns.
Your task is to return the size (area) of the maximum size submatrix which consists of all 1s i.e. the maximum area of a submatrix in which each cell has only the value ‘1’.
Note:1. Binary-valued matrix has either 0 or 1 in each cell.
2. A submatrix is a matrix formed by selecting certain rows and columns from a larger matrix.
In the above image, areas in green, red, and violet colour are all submatrices of the original 4x4 matrix.
3. The area of a matrix with 'H' rows and 'W' columns is equal to 'H' * 'W'.
The first line of the input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains two space-separated integers 'N' and 'M'.
Then each of the next 'N' lines of each test case contains 'M' space-separated integers(either 1 or 0).
Output Format:
Print the area of maximum size submatrix of all 1s in the given matrix.
Print the output of each test case in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 50
1 <= N, M <= 100
Time Limit: 1 sec
1
5 4
1 0 1 1
1 0 1 1
0 1 0 1
1 1 1 1
0 0 0 1
5
1
4 4
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
8
Can you use the “Largest rectangle in a histogram” technique to calculate the area?
The final algorithm will be-
O(N*M), where N denotes the number of rows of the matrix and M denotes the number of columns.
We will visit each cell of the binary matrix at most twice, hence the overall Time Complexity will be O(N*M).
O(M), where M denotes the number of columns.
We are using one 1-dimensional array/list of size M, the overall Space Complexity will be O(M).