Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Maximum size subrectangle

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
6 upvotes
Asked in company
Adobe

Problem statement

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.

subMatrix_image

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'. 
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 50
1 <= N, M <= 100

Time Limit: 1 sec
Sample Input 1:
1
5 4
1 0 1 1
1 0 1 1
0 1 0 1
1 1 1 1
0 0 0 1
Sample Output 1:
5
Explanation for Sample Input 1:

explanationSampleInput1

Sample Input 2:
1
4 4
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
Sample Output 2:
8
Full screen
Console